/* 一開始大意了 以為和bzoj上的祭祀是一樣的（畢竟樣例都一樣） 這里不知相鄰的點可以相互到達(dá) 間接相連的也可以到達(dá) 所以floyed先建立一下關(guān)系 再跑最大獨立集 下面貼一下95 和 100的代碼 （認(rèn)真讀題保平安） */ #include<iostream> #include<cstdio> #include<cstring> #define maxn 210 #define maxm 30010 using namespace std; int n,m,head[maxn],num,ans,match[maxn]; bool f[maxn]; struct node {int u,v,pre; }e[maxm]; void Add(int from,int to) {num++;e[num].u=from;e[num].v=to;e[num].pre=head[from];head[from]=num; } int Dfs(int s) {for(int i=head[s];i;i=e[i].pre){int v=e[i].v;if(f[v]==0){f[v]=1;if(match[v]==0||Dfs(match[v])){match[v]=s;return 1;}}}return 0; } int main() {scanf("%d%d",&n,&m);int x,y;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);Add(x,y);}for(int i=1;i<=n;i++){memset(f,0,sizeof(f));ans+=Dfs(i);}int p=n-ans;printf("%d\n",p);return 0; } #include<iostream> #include<cstdio> #include<cstring> #define maxn 210 using namespace std; int n,m,g[maxn][maxn],ans,match[maxn]; bool f[maxn]; int Dfs(int s) {for(int i=1;i<=n;i++)if(f[i]==0&&g[s][i]==1){f[i]=1;if(match[i]==0||Dfs(match[i])){match[i]=s;return 1;}}return 0; } int main() {scanf("%d%d",&n,&m);int x,y;ans=n;for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);g[x][y]=1;}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)g[i][j]=g[i][j]||(g[i][k]&&g[k][j]);for(int i=1;i<=n;i++){memset(f,0,sizeof(f));ans-=Dfs(i);}printf("%d\n",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/yanlifneg/p/5633169.html

總結(jié)

以上是生活随笔為你收集整理的codevs 2494 Vani和Cl2捉迷藏的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。