1 3 2 1 2 1 3
2
#include<stdio.h> #include<iostream> #include<vector> using namespace std; int vist[5005],match[5005]; vector<int>map[5005]; int find(int i) { for(int j=0;j<map[i].size();j++) if(vist[map[i][j]]==0) { vist[map[i][j]]=1; if(match[map[i][j]]==0||find(match[map[i][j]])) { match[map[i][j]]=i; return 1; } } return 0; } //-----下方是用强连通把环缩成一个点,使整个图变成有向无环图------ int stack[5005],sn,low[5005],dfn[5005],deep,node[5005],k; int Min(int a,int b) { return a>b?b:a; } void dfs(int i) { stack[++sn]=i; vist[i]=1; deep++; low[i]=dfn[i]=deep; for(int j=0;j<map[i].size();j++) if(vist[map[i][j]]==0) { dfs(map[i][j]); low[i]=Min(low[i],low[map[i][j]]); } else if(vist[map[i][j]]==1)//这个点在栈中 low[i]=Min(low[i],dfn[map[i][j]]); if(low[i]==dfn[i])//在栈中点i及到栈顶的点是一个强连通分量 { k++; while(stack[sn]!=i) { node[stack[sn]]=k; //表示原先的点stack[sn]在缩点后的图中是第k类点。 vist[stack[sn]]=2; //走过了,但己经出栈 sn--; } node[stack[sn]]=k; vist[stack[sn]]=2; sn--; } } int reSetMap(int n) { vector<int>mp[5005]; sn=0; deep=0; k=0; for(int j=1;j<=n;j++) vist[j]=0; for(int i=1;i<=n;i++) if(vist[i]==0) dfs(i); for(int i=1;i<=n;i++)//缩点构成新图 for(int j=0;j<map[i].size();j++) if(node[i]!=node[map[i][j]])//在新图中不是同一个点时 mp[node[i]].push_back(node[map[i][j]]); for(int i=1;i<=k;i++) map[i]=mp[i]; return k;//反回新图的点的个数 } int main() { int t,n,m,a,b,ans; scanf("%d",&t); while(t--) { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) map[i].clear(),match[i]=0; while(m--) { scanf("%d%d",&a,&b); map[a].push_back(b); } n=reSetMap(n);//缩点构成新的有向无环图 ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++)vist[j]=0; ans+=find(i); } printf("%d\n",n-ans); } }
hdu3861The King’s Problem (强连通 缩点+最小路径覆盖),布布扣,bubuko.com
hdu3861The King’s Problem (强连通 缩点+最小路径覆盖)
原文:http://blog.csdn.net/u010372095/article/details/38348613