首页 > ACM题库 > HDU-杭电 > HDU 3517-Adopt or not[解题报告]HOJ
2014
11-05

HDU 3517-Adopt or not[解题报告]HOJ

Adopt or not

问题描述 :

A two-party system is a form of party system where two major political parties dominate voting in nearly all elections, at every level. As a result, all, or nearly all, elected offices end up being held by candidates endorsed by one of the two major parties.Under a two-party system, one of the two parties typically holds a plurality in the legislature , and is referred to as the majority party. The smaller party is referred to as the minority party. Two-party systems are most common in polities with plurality vote counting system to prevent the problem of two similar candidates "splitting" the same voters.
There is a small country under a two-party system, the two parties are party A and party B. Every time when parliament convened, members of both parties will submit Their proposals. Some of the proposals will be raised by some members of the same party, but each person can submit only one. Of course, some people may object to certain proposals of the other party. If a member’s proposal is adopted and all his objection cases are not adopted, then he will be pleased. As the country’s president, you can arrange these proposals is adopted or not. You want to know , to make the numnber of people pleased with your decision maximum, which proposals must be adopted ?

输入:

On the first line one positive number: the number of testcases. After that per testcase:One line with three integers a, b, n (0<=a,b<=100 and 0<=n<=200): the number of proposals by party A, by party B, and number of members of the parliament. The proposals are numbered from 1 to a+b, the first a are party A’s, the latter b are party B’s.
n lines follow, each line represents a member of the parliament, begin with two integers ri,mi(1<=ri<=a+b, 0<=mi<a+b): the proposal submit by him, the number of proposals he object to. And then follows mi integers indicate the proposal he object to.

输出:

On the first line one positive number: the number of testcases. After that per testcase:One line with three integers a, b, n (0<=a,b<=100 and 0<=n<=200): the number of proposals by party A, by party B, and number of members of the parliament. The proposals are numbered from 1 to a+b, the first a are party A’s, the latter b are party B’s.
n lines follow, each line represents a member of the parliament, begin with two integers ri,mi(1<=ri<=a+b, 0<=mi<a+b): the proposal submit by him, the number of proposals he object to. And then follows mi integers indicate the proposal he object to.

样例输入:

3
2 1 3
1 0
1 0
3 0
2 1 3
1 0
2 1 3
3 0
2 1 4
1 0
1 1 3
2 0
3 2 1 2

样例输出:

3
2 1 3
2 
1 1
3 
2 1 2 

Hint
In case 2,the first people is happy only if proposal 1 is adopted;the second people is happy if proposal 2 is adopted and proposal 3 isn't; the third people is happy only if proposal 3 is adopted;The maxium number is 2, there are 2 ways to get 2 people happy. Adopt proposal 1 and 2, or 1 and 3. So,we can see that only proposal 1 must be adopted.

#include <iostream>  
#include <cstring>  
#include <string>  
#include <algorithm>  
#include <vector>
#include <cstdio>
using namespace std;  
#define maxn MAXN
const int MAXN = 508;  

int G[MAXN][MAXN];//chengyuanguanxi
int mx[maxn],my[maxn];//yuanshizuidapipei
int used[MAXN];
int ansX[maxn],ansY[maxn];
int delX,delY;
struct per
{
	int dislike[maxn];
	int like;
	int dp;
};
per person[maxn];
int X[maxn],Y[maxn];
int nx,ny;
int shuchu[maxn];
int shuchu2[maxn];
#define clr(x) memset(x,0,sizeof(int)*MAXN)
#define _clr(x) memset(x,0xff,sizeof(int)*MAXN)
int hungray(int m,int n,int mat[][maxn],int *match1,int *match2)
{
	int s[maxn],t[maxn],p,q,ret=0,i,j,k;
	for(_clr(match1),_clr(match2),i=0;i<m;ret+=(match1[i++]>=0))
		for(_clr(t),s[p=q=0]=i;p<=q&&match1[i]<0;p++)
			for(k=s[p],j=0;j<n&&match1[i]<0;j++)
				if(mat[k][j]&&t[j]<0)
				{
					s[++q]=match2[j],t[j]=k;
					if(s[q]<0)
						for(p=j;p>=0;j=p)
							match2[j]=k=t[j],p=match1[k],match1[k]=j;
				}
	return ret;
}

bool Find(int v)
{ 
	for(int u=0;u<ny;u++)
	{
		if(!used[u]&&G[v][u])
		{ 
			used[u]=1;
				if(my[u]==-1||Find(my[u]))
				{
					mx[v]=u;my[u]=v; return 1;
				}
		}
	}
	return 0;
}
bool FindY(int v)
{ 
	for(int u=0;u<ny;u++)
	{
		if(u!=delY&&!used[u]&&G[v][u])
		{
			used[u]=1;
				if(my[u]==-1||FindY(my[u]))
				{
					return 1;
				} 
		}
	}
	return 0;
}
bool FindX(int u)
{
	for(int v=0;v<nx;v++)
	{ if(v!=delX&&!used[v]&&G[v][u])
		{
			used[v]=1;
				if(mx[v]==-1||FindX(mx[v]))
					return 1;
		}
	}
	return 0;
}
int MMG()
{
	for(int i=0;i<nx;i++)mx[i]=-1;
		for(int j=0;j<ny;j++)my[j]=-1;
			int sum=0;
				for(int i=0;i<nx;i++)
				{
					clr(used);
						if(Find(i))
							sum++;
				}
	return sum;
} 
void Work()
{
	//hungray(nx,ny,G,mx,my);
		printf("%d\n",nx+ny-MMG());
		clr(ansX);
		clr(ansY);
		for(int i=0;i<nx;i++)
		{ if(mx[i]==-1)
			{
				//非必须点 
				ansX[i]=1;
			}
			else
			{
				delY=mx[i];
					clr(used);
					if(FindY(i))ansY[delY]=1;//增广成功,非必须点,注意找到的点属于哪个 集合,不要搞反了。
			}
		}
	for(int j=0;j<ny;j++)
	{
		if(my[j]==-1)
			ansY[j]=1;
		else
		{
			delX=my[j];
				clr(used);
				if(FindX(j))ansX[delX]=1;//增广成功,非必须点 
		} 
	} 
} 



int main()  
{ 
	int T;
	scanf("%d",&T);
	while(T--)
	{
		int a,b,p;
		scanf("%d%d%d",&a,&b,&p);
		memset(G,0,sizeof(G));
		memset(person,0,sizeof(person));
		clr(shuchu2);
		clr(shuchu);
		int like,num;
		nx=0,ny=0;
		for(int i=0;i<p;i++)
		{
			scanf("%d",&like);
			if(like>a)
			{
				X[nx++]=i;
			}
			else 
			{
				Y[ny++]=i;
			}
			person[i].like=like;
			scanf("%d",&person[i].dp);
			for(int j=0;j<person[i].dp;j++)
				scanf("%d",&person[i].dislike[j]);
		}


		/*
		for(int t=0;t<nx+ny;t++)
		{
			printf("like %d ",person[t].like);
			printf("dp%d ",person[t].dp );
			for(int tt=0;tt<person[t].dp;tt++)
			{
				printf(" %d",person[t].dislike[tt]);
				puts("");
			}
		}
		*/


		for(int i=0;i<nx;i++)
		{
			for(int j=0;j<ny;j++)
			{
				for(int t=0;t<person[Y[j]].dp;t++)
				{
					if(person[X[i]].like==person[Y[j]].dislike[t])
					{
						G[i][j]=1;break;
					}
				}
				if(G[i][j]==0)
				for(int t=0;t<person[X[i]].dp;t++)
				{
					if(person[Y[j]].like==person[X[i]].dislike[t])
					{
						G[i][j]=1;break;
					}
				}
			}
		}
		/*
		for(int i=0;i<nx;i++)
		{
			for(int j=0;j<ny;j++)
			{
				printf("%d ",G[i][j]);
			}
			puts("");
		}
		*/
		Work();
		int ipsc=0;
		for(int t=0;t<nx;t++)
		{
			if(ansX[t]==1)
			{
				shuchu[ipsc++]=person[X[t]].like;
			}
		}
		for(int t=0;t<ny;t++)
		{
			if(ansY[t]==1)
			{
				shuchu[ipsc++]=person[Y[t]].like;
			}
		}
		sort(shuchu,shuchu+ipsc);
		int ipsc2=0;
		if(ipsc>0)
		{
			shuchu2[ipsc2++]=shuchu[0];
		}
		for(int t=1;t<ipsc;t++)
		{
			if(shuchu[t]!=shuchu[t-1])
			{
				shuchu2[ipsc2++]=shuchu[t];
			}
		}
		printf("%d",ipsc2);
		for(int t=0;t<ipsc2;t++)
		{
				printf(" %d",shuchu2[t]);
		}
		printf("\n");
	}
	return 0;  
}