二分图&匈牙利算法

发表于

author:tc
勤劳的tc来了首先是二分图
他主要是有两个顶点集，然后顶点之间不能连接起来。？。。
怎么判断它是二分图？。。
先将一个一个点标记为1（或者0）然后与它连接起来的为标记的的就标记为0（或者1），如果该点已经标记，则判断他是否和顶点的值相同，相同则不为二分图，反之则是是。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
bool is_two() {
	queue<int> que;
	que.push(1);
	int from;
	visit[1]=1;
	while(!que.empty()) {
		from=que.front();
		que.pop();
		int i=1;
		for(i; i<=n; i++) {
			if(map[from][i]) {
				if(!visit[i]) {
					que.push(i);
					visit[i]=(visit[from]&1)+1;
				} else if(visit[i]==visit[from]) {
					return false;
				}
			}
		}
	}
	return true;
}
```  
匈牙利算法主要是解决是二分图匹配问题。  
一个顶点可以与多个结点相连。如果一个顶点只连接一个顶点求最多可以连接多少。  
假如 a可以和c,d,e,f相连，h可以和c,d,m,n,  z可以和c,d,k相连。
首先先匹配a和c。  
第二步是匹配h，h不能喝c匹配，但是h并不想换人，所以就返回去看a能不能换a没办法只能换一个换到了d，h匹配到了c。最后就是z了，他也想匹配c，可是他也不想换，只能h换了，h换成了d可是d又和a匹配了，h也不想换之后a换了，a最后换成了e。最后a，h，z都匹配好了。  
当然这个换人的过程是用递归实现的。

bool find(int x) {
int j=1;
for(; j<=n; j++) {
if(map[x][j]&&!visit[j]) {
visit[j]=true;
if(!match[j]||find(match[j])) {
match[j]=x;
return true;
}
}
}
return false;
}

1
2
3
4
5
6
7
8
9
10
以下是题目:  
[hdu2444](http://acm.hdu.edu.cn/showproblem.php?pid=2444)   
这道题先要判断是否为二分图，否的话输出-1

include

include

include

using namespace std;

//bool find()

int map[205][205];

int match[205];
int visit[205];

int n,m;

bool find(int x) {
int j=1;
for(; j<=n; j++) {
if(map[x][j]&&!visit[j]) {
visit[j]=true;
if(!match[j]||find(match[j])) {
match[j]=x;
return true;
}
}
}
return false;
}

bool is_two() {
queue que;
que.push(1);
int from;
visit[1]=1;
while(!que.empty()) {
from=que.front();
que.pop();
int i=1;
for(i; i<=n; i++) {
if(map[from][i]) {
if(!visit[i]) {
que.push(i);
visit[i]=(visit[from]&1)+1;
} else if(visit[i]==visit[from]) {
return false;
}
}
}
}
return true;
}

int main() {
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
while(cin>>n>>m) {
memset(map,0,sizeof map);
memset(match,0,sizeof match);
memset(visit,0,sizeof visit);
int i=0,one,two;
for(; i>one>>two;
map[one][two]=1;
map[two][one]=1;
}
int ans=0;
if(!is_two()||n==1) {
cout<<”No”<<endl;
continue;
}
for(int i=1; i<=n; i++) {
memset(visit,0,sizeof visit);
ans+=find(i);
}
cout<<ans/2<<endl;
}
return 0;
}
```