pku 3014 &&pku 1325

it2022-05-06  4

pku 3014

题意:有个rc列的棋盘,上面的某些方格中有怪物,现在你能做的一次操作是将其中一行或一列的怪物都消灭掉,问将所有怪物都消灭掉的最少次数是多少

pku 1325

题意:

A B两台机器分别有n,m(0n-1, 0m-1)种工作模式,初始时都处于0模式。而且如果机器要改变模式,必须重启(重启就是回到0模式)。现在有k任务,每个任务都可以被AB的某些模式完成。

问最少需要重启多少次? 分析:倆道题目我们都可以这样理解: 第一个题目: 在棋盘上的每一个怪物,都可选择被该行消灭还是被该列消灭,这是行与列就是一种匹配; 而第二个题目:对与每一个任务,有俩种选择,可以选择被A的某种模式或者B的某种模式完成,这时,这俩种模式便是一种匹配; 那么问题就顺理成章的转变为求最小覆盖数了,(选择最小的行或列,选择最小的模式),而最小覆盖数又等于最大匹配数,这样问题就解决了 pku 3014 #include<iostream>using namespace std;int n,match[510];bool vis[510],g[510][510];int path(int s){for(int i=1;i<=n;i++) {if(g[s][i]&&!vis[i]) { vis[i]=1;if(match[i]==-1||path(match[i])) { match[i]=s;return 1; } } }return 0;}int main(){int k,a,b;while(scanf("%d %d",&n,&k)==2) { memset(g,0,sizeof(g)); memset(match,-1,sizeof(match));for(int i=0;i<k;i++) { scanf("%d %d",&a,&b); g[a][b]=1; }int ans=0;for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); ans+=path(i); } printf("%d\n",ans); }return 0;}

pku 1325

pku1325 #include<iostream>#include<stdio.h>#include<string.h>#include<stdlib.h>using namespace std;bool g[210][210],vis[210];int match[210],n,m,k;int path(int s){for(int i=1;i<=m;i++)if(g[s][i]&&!vis[i]) { vis[i]=1;if(match[i]==-1||path(match[i])) { match[i]=s;return 1; } }return 0;}int main(){int a,b,c;while(scanf("%d",&n)==1&&n) { scanf("%d %d",&m,&k); memset(g,0,sizeof(g)); memset(match,-1,sizeof(match));for(int i=1;i<=k;i++) { scanf("%d %d %d",&a,&b,&c); g[b][c]=1; }int ans=0;for(int i=1;i<=n;i++) { memset(vis,0,sizeof(vis)); ans+=path(i); } printf("%d\n",ans); }return 0;}

转载于:https://www.cnblogs.com/nanke/archive/2011/08/25/2153280.html

相关资源:poj pku 解题报告

最新回复(0)