POJ 3715 Blue and Red 二分图
来源：程序员人生 发布时间：2015-01-29 08:39:53 阅读次数：3451次
说是有1个军事演习
n个兵士，其中有m个关系表示某两个人是好友
现在兵士已分好了两组了，用来进行对抗，但是这两组之间可能有好友，会影响军事演习的情况
所以要去掉尽可能少的人，使得这个两组之间没有好友。
那末题目给了1个分组方案了， 但是不同组之间可能有好友，
我们就要在这些个不同组的好友之间 连边然后求2分图最大匹配，
求出来的结果就是要去掉的人数
但是题目又要求字典序要最小。
那我们就从序号小的开始枚举， 摹拟删除掉该人， 然后求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;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
