POJ 3715 Blue and Red 二分圖
來源：程序員人生 發(fā)布時間：2015-01-29 08:39:53 閱讀次數(shù)：3627次
說是有1個軍事演習(xí)
n個兵士，其中有m個關(guān)系表示某兩個人是好友
現(xiàn)在兵士已分好了兩組了，用來進(jìn)行對抗，但是這兩組之間可能有好友，會影響軍事演習(xí)的情況
所以要去掉盡可能少的人，使得這個兩組之間沒有好友。
那末題目給了1個分組方案了， 但是不同組之間可能有好友，
我們就要在這些個不同組的好友之間 連邊然后求2分圖最大匹配，
求出來的結(jié)果就是要去掉的人數(shù)
但是題目又要求字典序要最小。
那我們就從序號小的開始枚舉， 摹擬刪除掉該人， 然后求2分圖最大匹配看有無變化， 如果有變化說明這個人必須去掉
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
#include <cmath>
#include <algorithm>
#include <map>
#include <ctime>
#define MAXN 222
#define MAXM 6122222
#define INF 1000000001
using namespace std;
int n, m;
vector<int>g[MAXN], ans;
int mark[MAXN], used[MAXN], cx[MAXN], cy[MAXN], a[MAXN];
int path(int u)
{
int sz = g[u].size();
for(int i = 0; i < sz; i++)
{
int v = g[u][i];
if(!mark[v] && !used[v])
{
mark[v] = 1;
if(cy[v] == ⑴ || path(cy[v]))
{
cx[u] = v;
cy[v] = u;
return 1;
}
}
}
return 0;
}
int gao()
{
int ans = 0;
memset(cy, ⑴, sizeof(cy));
for(int i = 1; i <= n; i++)
{
memset(mark, 0, sizeof(mark));
if(a[i] || used[i]) continue;
ans += path(i);
}
return ans;
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) g[i].clear();
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
int u, v;
for(int i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
u++, v++;
if(a[u] != a[v]) {
if(a[u] == 0) {
g[u].push_back(v);
} else {
g[v].push_back(u);
}
}
}
memset(used, 0, sizeof(used));
ans.clear();
int d = gao();
for(int i = 1; i <= n; i++) {
used[i] = 1;
int z = gao();
if(z < d) {
ans.push_back(i);
d = z;
} else used[i] = 0;
}
printf("%d", ans.size());
for(int i = 0; i < ans.size(); i++) printf(" %d", ans[i] - 1);
printf("
");
}
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈
