pku 3014
题意：有个r行c列的棋盘，上面的某些方格中有怪物，现在你能做的一次操作是将其中一行或一列的怪物都消灭掉，问将所有怪物都消灭掉的最少次数是多少？
pku 1325
题意：
A B两台机器分别有n,m(0…n-1, 0…m-1)种工作模式，初始时都处于0模式。而且如果机器要改变模式，必须重启（重启就是回到0模式）。现在有k个任务，每个任务都可以被A或B的某些模式完成。
问最少需要重启多少次？ 分析：倆道题目我们都可以这样理解： 第一个题目: 在棋盘上的每一个怪物，都可选择被该行消灭还是被该列消灭，这是行与列就是一种匹配； 而第二个题目：对与每一个任务，有俩种选择，可以选择被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 解题报告