hdu 3829 Cat VS Dog

この問題が上がったばかりで読んだこの問題は、シミュレーションで書いたり書いたりして、欲張りで書いたりしています...私は抽象的に図になって、それから最も多くの(つまり最も嫌いな人に最も多い)を削除して、それからこのように削除して、WA、また削除して最も好きなことに変えて、やはりWA..どうやってYYもだめT T..
それから他の問題を見に行きました.
群の中でこの問題が二分マッチング==..二分マッチング...どうしても思い出せない.
また別の問題を見に行きました...本当に木の問題ができた.これを見に帰ります.
図を作る方法をたくさん考えて、うっとうしくてたまらない.
後で考えて、もし子供1がD 1が好きで、子供2がD 1が嫌いなら、この2つの建辺は、このようにして、それから結果は定点数-最大マッチング数です.
そしてこのように建てられました、WA.泣く.もともと子供を建てなくてもいいと思っていた1 KKと子供xがKKが好きな辺が嫌いで、前に建てたはずなので、後で建てた図を出力して、非対称Tを発見しました..確かにこれっぽっちの間違いで、直したらAが落ちます.
ネット上を探したばかりで、彼らは私とは違って、猫と犬を建てました.私はまた黒い本をめくって、最小の経路が最大の独立集神馬を覆っているのはいつもはっきりしていません.今は理解しました.
これは最大の独立集哈で、さっきグループの中の同級生に聞いて、彼の解惑に感謝しました.
最大独立セット:セット内の任意の2つの要素には関係がありません(または、指定した矛盾関係がありません)、最大独立セット=頂点数-最大一致.
だから一人を分解して、関係を確立して、求めた答えは頂点数-最大マッチング数/2です.求めた関係は必ず各点に2回含まれるからだ.

#include <queue>
#include <stack>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <limits.h>
#include <string.h>
#include <string>
#include <algorithm>

using namespace std;

const int MAX = 750;

int map[MAX][MAX];
int a[MAX][MAX];
int used[MAX],mat[MAX];
int Augment(int s,int n,int x)
{
	int i;
	for(i=s; i<n; i++)
		if( !used[i] && a[x][i] )
		{
			used[i] = 1;
			if( mat[i] == -1 || Augment(s,n,mat[i]) )
			{
				mat[i] = x;
				return 	1;
			}
		}
	return 0;
}

int Hungary(int s,int n)
{
	int i,sum = 0;
	memset(mat,-1,sizeof(mat));
	for(i=s; i<n; i++)
	{
		memset(used,0,sizeof(used));
		if( Augment(s,n,i) )
			sum++;
	}
	return sum;
}
int main()
{
	int n,m,p,cnt;
	char s[150],ch;
	while( ~scanf("%d%d%d",&n,&m,&p) )
	{
		memset(map,0,sizeof(map));
		memset(a,0,sizeof(a));
		for(int i=0; i<p; i++)
		{
			int k;
			scanf("%s",s);
			sscanf(s,"%c%d",&ch,&k);
			if( ch == 'C' )
				map[i][p+k-1] = 1;
			else
				map[i][p+n+k-1] = 1;
			scanf("%s",s);
			sscanf(s,"%c%d",&ch,&k);
			if( ch == 'C' )
				map[p+k-1][i] = 1;
			else
				map[p+n+k-1][i] = 1;
		}
		cnt = n + m + p;
		for(int i=0; i<p; i++)
		{
			for(int k=p; k<cnt; k++)
				if( map[i][k] )
					for(int l=0; l<p; l++)
						if( map[k][l] )
							a[i][l] = 1;
			for(int k=p; k<cnt; k++)
				if( map[k][i] )
					for(int l=0; l<p; l++)
						if( map[l][k] )
							a[i][l] = 1;
		}
		int ans = Hungary(0,p);
		printf("%d
",p-ans/2);
	}

return 0;
}