最大独立集 = 总的点数 - 最小覆盖集 = 总的点数 - 最大流
匈牙利算法
#include<cstdio> #include<cstring> using namespace std; #define N 205 int g[N][N]; int match[N]; int vis[N]; int n,m,k; int dfs(int u) { for(int i=1;i<=m;i++) if(!vis[i] && !g[u][i]){ vis[i]=1; if(match[i]==-1 || dfs(match[i])){ match[i]=u; return 1; } } return 0; } int hungary() { int ret=0; memset(match,-1,sizeof(match)); for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); ret+=dfs(i); } return ret; } int main(void) { int a,b; int cas=1; while(scanf("%d%d%d",&n,&m,&k)&&(n+m+k)) { memset(g,0,sizeof(g)); for(int i=0;i<k;i++){ scanf("%d%d",&a,&b); g[a][b]=1; } printf("Case %d: %d\n",cas++,n+m-hungary()); } return 0; }网络流样例没过。。。很难受，先挖个坑吧。。。
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int N = 20000; const int INF = 1e9; struct Node{ int ne; int to; int w; }e[N<<1]; int head[N],deth[N]; int x,y,val,cnt,n,m,k,st,en; void init() { memset(head,-1,sizeof(head)); cnt = 0; st = 0; en = n + m + 10; } void add(int u,int v,int val) { e[cnt].to = v; e[cnt].ne = head[u]; e[cnt].w = val; head[u] = cnt ++; } bool bfs() { memset(deth,0,sizeof(deth)); queue<int>q; q.push(st); deth[st] = 1; while(!q.empty()) { int now = q.front(); q.pop(); for(int i=head[now];~i;i=e[i].ne) { int to = e[i].to; if(deth[to] == 0 && e[i].w > 0) { deth[to] = deth[now] + 1; q.push(to); } } } if(deth[en] == 0) return 0; return 1; } int dfs(int u,int dist) { if(u == en) return dist; int temp = dist; for(int i=head[u];~i;i=e[i].ne) { int to = e[i].to; if(deth[to] == deth[u] + 1 && e[i].w) { int di = dfs(to,min(e[i].w,temp)); if(di > 0) { temp -= di; e[i].w -= di; e[i^1].w += di; if(temp <= 0) return dist; } } } return dist - temp; } int dinic() { int ans = 0; while(bfs()) { while(int di = dfs(st,INF)) ans += di; } return ans; } int main() { int tot = 0; while(scanf("%d%d%d",&n,&m,&k) && n+m+k) { init(); for(int i=1;i<=k;i++) { scanf("%d%d",&x,&y); add(x,y,1); add(y,x,0); } for(int i=1;i<=n;i++) { add(st,i,1); add(i,st,0); } for(int i=1;i<=m;i++) { add(i+n,en,1); add(en,i+n,0); } int kk = dinic(); printf("Case %d: %d\n",++tot,n+m-kk); } return 0; }好吧，这个题要反向建图！还有，这个题竟然卡网络流！！！
#include<iostream> #include<cstdio> #include<queue> #include<cstring> #include<algorithm> using namespace std; const int N = 200; const int INF = 1e9; struct Node{ int ne; int to; int w; }e[N<<1]; int head[N],deth[N]; int mp[N][N]; int x,y,val,cnt,n,m,k,st,en; void init() { memset(head,-1,sizeof(head)); memset(mp,0,sizeof(mp)); cnt = 0; st = 0; en = n + m + 10; } void add(int u,int v,int val) { e[cnt].to = v; e[cnt].ne = head[u]; e[cnt].w = val; head[u] = cnt ++; } bool bfs() { memset(deth,0,sizeof(deth)); queue<int>q; q.push(st); deth[st] = 1; while(!q.empty()) { int now = q.front(); q.pop(); for(int i=head[now];~i;i=e[i].ne) { int to = e[i].to; if(deth[to] == 0 && e[i].w > 0) { deth[to] = deth[now] + 1; q.push(to); } } } if(deth[en] == 0) return 0; return 1; } int dfs(int u,int dist) { if(u == en) return dist; int temp = dist; for(int i=head[u];~i;i=e[i].ne) { int to = e[i].to; if(deth[to] == deth[u] + 1 && e[i].w) { int di = dfs(to,min(e[i].w,temp)); if(di > 0) { temp -= di; e[i].w -= di; e[i^1].w += di; if(temp <= 0) return dist; } } } return dist - temp; } int dinic() { int ans = 0; while(bfs()) { while(int di = dfs(st,INF)) ans += di; } return ans; } int main() { int tot = 0; while(scanf("%d%d%d",&n,&m,&k) && n+m+k) { init(); for(int i=1;i<=k;i++) { scanf("%d%d",&x,&y); mp[x][y] = 1; } for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { if(!mp[i][j]) { add(i,j+n,1); add(j+n,i,0); } } } for(int i=1;i<=n;i++) { add(st,i,1); add(i,st,0); } for(int i=1;i<=m;i++) { add(i+n,en,1); add(en,i+n,0); } int kk = dinic(); printf("Case %d: %d\n",++tot,n+m-kk); } return 0; }