bzoj 2718: [Violet 4] （floyed+匈牙利算法）

Description

Input

Output

最多可选多少景点

Sample Input

Sample Output

HINT

Source

Ctsc2008 River & ural 1533. Fat Hobbits

#include<iostream>#include<cstdio>#include<algorithm>#include<cstring>#define N 203using namespace std;int n,m,f[N][N],tot;int point[N*2],nxt[N*N],v[N*N];int vis[N*N],belong[N*2];void add(int x,int y){	tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;}bool find(int x,int k){	for (int i=point[x];i;i=nxt[i]){		int j=v[i];		if (vis[j]==k) continue;		vis[j]=k;		if (find(belong[j],k)||!belong[j]) {			belong[j]=x;			return true;		}	}	return false;}int main(){	freopen("a.in","r",stdin);	scanf("%d%d",&n,&m);	for (int i=1;i<=m;i++) {		int x,y; scanf("%d%d",&x,&y);		f[x][y]=1;	}	for (int k=1;k<=n;k++)	 for (int i=1;i<=n;i++)	  for (int j=1;j<=n;j++)	   if (i!=j&&j!=k&&k!=i)	    if (f[i][k]&&f[k][j]) f[i][j]=1;	for (int i=1;i<=n;i++)	 for (int j=1;j<=n;j++) 	  if (f[i][j]) {	  	add(i,j+n);	  }	int size=0;	for (int i=1;i<=n;i++)	 if (find(i,i)) size++;	PRintf("%d/n",n-size); }