二分匹配解決poj 1466
Description
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.
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
7 0: (3) 4 5 6 1: (2) 4 6 2: (0) 3: (0) 4: (2) 0 1 5: (1) 0 6: (2) 0 1 3 0: (2) 1 2 1: (1) 0 2: (1) 0
Sample Output
5 2
題意：在大學校園里男女學生存在某種關系，現在給出學生人數n，并給出每個學生與哪些學生存在關系（存在關系的學生一定是異性）。現在讓你求一個學生集合，這個集合中任意兩個學生之間不存在這種關系。輸出這樣的關系集合中最大的一個的學生人數。
思路：對于給定的人數n，我們可以看成兩個集合a和b，每個集合中有n個人，對于a中的每個元素，和b中的某些元素存在關系（邊）（也就是每個人和其它人的關系，），而且這兩個點集及關系構成的圖必定是一個二分圖。如果我們求出二分圖的最大匹配對數，那么將總元素個數減去最大匹配個數，剩下的個數就是最大獨立集元素的個數。此題中我們將人數擴大了兩倍（構建二分圖的需要），所經結果應該除以二。最以最終答案的公式應該是：max=n-最大匹配數/2;
View Code
#include <iostream>
using namespace std;
const int N=510;
struct edge
{
int to,nxt;
}e[N*N];
int p[N],mch[N];
bool vis[N];
bool dfs(int u) //u就是from, v就是to
{
for(int x=p[u];x!=-1;x=e[x].nxt)
{
int v=e[x].to;
if(!vis[v])
{
vis[v]=true;
if(mch[v]==-1||dfs(mch[v]))
{
mch[v]=u;
return true;
}
}
}
return false;
}
int main()
{
int n;
while(~scanf("%d",&n))
{
int i,j=0;
memset(p,-1,sizeof(p));
for(i=0;i<n;i++)
{
int x,num;
scanf("%d: (%d)",&num,&num);
for(int k=1;k<=num;k++)
{
scanf("%d",&x);
e[j].to=x;e[j].nxt=p[i];p[i]=j++;
}
}
cout<<j<<endl;
memset(mch,-1,sizeof(mch));
int ans=0;
for(i=0;i<n;i++)
{
memset(vis,0,sizeof(vis));
if(dfs(i))
ans++;
}
printf("%d\n",n-ans/2);
}
return 0;
}
posted on 2012-03-16 18:58 More study needed. 閱讀(463) 評論(0) 收藏 舉報
浙公網安備 33010602011771號