POJ 3715 Blue and Red 二分图
发布时间：2020-12-13 20:13:14 所属栏目：PHP教程 来源：网络整理
导读：说是有1个军事演习 n个兵士，其中有m个关系表示某两个人是好友 现在兵士已分好了两组了，用来进行对抗，但是这两组之间可能有好友，会影响军事演习的情况 所以要去掉尽可能少的人，使得这个两组之间没有好友。 那末题目给了1个分组方案了， 但是不同组之间可
|
说是有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,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,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;
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |