Girls and Boys
Time Limit: 5000ms
Memory Limit: 10000KB
This problem will be judged on PKU. Original ID: 64-bit integer IO format: %lld Java class name: Main In the second year of the university somebody started a study on the romantic (浪漫的) relations between the students. The relation " romantically (浪漫地) involved (包含)" is defined (定义) between one girl and one boy. For the study reasons it is necessary to find out the maximum set satisfying the condition: there are no two students in the set who have been "romantically involved". The result of the program is the number of students in such a set.
Input
The input (投入) contains several data sets in text format. Each data set represents one set of subjects of the study, with the following description: the number of students the description of each student, in the following format student_ identifier (标识符):(number_of_romantic_relations) student_identifier1 student_identifier2 student_identifier3 ... or student_identifier:(0) The student_identifier is an integer (整数) number between 0 and n-1 (n <=500 ), for n subjects.
Output
For each given data set, the program should write to standard output (输出) a line containing the result.
Sample Input
70: (3) 4 5 61: (2) 4 62: (0)3: (0)4: (2) 0 15: (1) 06: (2) 0 130: (2) 1 21: (1) 02: (1) 0
Sample Output
52
题目大意：有n个人每个人又和别的人有关系，求的是没有关系的最大人数。
输入：
第一行 n个人，接下来n行 0--n-1:(与此人有关系的人的个数 ) 有关系的人。
求的是二分图的最大独立集，此题不用划分集合，所以最后的最大匹配数要除以2。
二分图最大独立集 = N - 最大匹配数。
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 const int INF=2147483647; 8 const int maxn=2010,maxm=27010; 9 int cnt,fir[maxn],nxt[maxm],cap[maxm],to[maxm],dis[maxn],gap[maxn],path[maxn]; 10 11 void addedge(int a,int b,int c) 12 { 13 nxt[++cnt]=fir[a]; 14 to[cnt]=b; 15 cap[cnt]=c; 16 fir[a]=cnt; 17 } 18 19 bool BFS(int S,int T) 20 { 21 memset(dis,0,sizeof(dis)); 22 dis[T]=1; 23 queue q;q.push(T); 24 while(!q.empty()) 25 { 26 int node=q.front();q.pop(); 27 for(int i=fir[node];i;i=nxt[i]) 28 { 29 if(dis[to[i]])continue; 30 dis[to[i]]=dis[node]+1; 31 q.push(to[i]); 32 } 33 } 34 return dis[S]; 35 } 36 int fron[maxn]; 37 int ISAP(int S,int T) 38 { 39 if(!BFS(S,T)) 40 return 0; 41 for(int i=1;i<=T;i++)++gap[dis[i]]; 42 int p=S,ret=0; 43 memcpy(fron,fir,sizeof(fir)); 44 while(dis[S]<=T) 45 { 46 if(p==T){ 47 int f=INF; 48 while(p!=S){ 49 f=min(f,cap[path[p]]); 50 p=to[path[p]^1]; 51 } 52 p=T;ret+=f; 53 while(p!=S){ 54 cap[path[p]]-=f; 55 cap[path[p]^1]+=f; 56 p=to[path[p]^1]; 57 } 58 } 59 int &ii=fron[p]; 60 for(;ii;ii=nxt[ii]){ 61 if(!cap[ii]||dis[to[ii]]+1!=dis[p]) 62 continue; 63 else 64 break; 65 } 66 if(ii){ 67 p=to[ii]; 68 path[p]=ii; 69 } 70 else{ 71 if(--gap[dis[p]]==0)break; 72 int minn=T+1; 73 for(int i=fir[p];i;i=nxt[i]) 74 if(cap[i]) 75 minn=min(minn,dis[to[i]]); 76 gap[dis[p]=minn+1]++; 77 fron[p]=fir[p]; 78 if(p!=S) 79 p=to[path[p]^1]; 80 } 81 } 82 return ret; 83 } 84 85 void Init() 86 { 87 memset(fir,0,sizeof(fir)); 88 cnt=1; 89 } 90 int main() 91 { 92 int n,k,to; 93 while(~scanf("%d",&n)) 94 { 95 Init(); 96 for(int i=1;i<=n;i++)addedge(0,i,1),addedge(i,0,0),addedge(i+n,2*n+1,1),addedge(2*n+1,i+n,0); 97 for(int i=0;i
当然，匈牙利算法是更合适的算法~~~
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 const int INF=2147483647; 8 const int maxn=2010,maxm=27010; 9 10 int cnt,fir[maxn],nxt[maxm],to[maxm],match[maxn],vis[maxn];11 12 void addedge(int a,int b)13 {14 nxt[++cnt]=fir[a];15 to[cnt]=b;16 fir[a]=cnt;17 }18 19 int Hungary_algorithm(int node)20 {21 vis[node]=true;22 for(int i=fir[node];i;i=nxt[i]){23 if(!match[to[i]]){24 match[to[i]]=node;25 return 1;26 }27 if(!vis[match[to[i]]]&&Hungary_algorithm(match[to[i]])){28 match[to[i]]=node;29 return 1;30 } 31 } 32 return 0;33 } 34 35 void Init()36 {37 memset(fir,0,sizeof(fir));38 memset(match,0,sizeof(match));39 cnt=1;40 }41 42 int main()43 {44 int n,k,to,ans;45 while(~scanf("%d",&n))46 {47 Init();ans=0;48 for(int i=0;i