Posted on 2010-08-08 19:34
Uriel 阅读(383)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
图论
想到二分图，但是不知道那种贪心思想对不对以及如何优化。。参考了解题报告
感谢大牛的解题报告：
http://hi.baidu.com/liuzhe/blog/item/793e0c24efa6602cd407428a.html基本上照着写的，然后加了读入输出优化，效果惊人。。0MS。。暂时Rank1了。。还是头一次刷到这么前。。
//Problem: 3715 User: Uriel
//Memory: 444K Time: 0MS
//Language: G++ Result: Accepted
//Bipartite Graph Matching
//Hungary
//2010.08.08
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
short n,m,index;
bool type[205],a[205][205];
short l[205],ln;
struct node
{
short id;
node *next;
}*head[205],table[30005];
inline void add(int x,int y){
table[index].id=y;
table[index].next=head[x];
head[x]=&table[index];
index++;
}
int in()
{
char ch;
int a=0;
while((ch=getchar())==' ' || ch=='\n');
a*=10;
a+=ch-'0';
while((ch=getchar())!=' ' && ch!='\n')
{
a*=10;
a+=ch-'0';
}
return a;
}
void out(int a)
{
if(a>=10)out(a/10);
putchar(a%10+'0');
}
void Build_Graph(){
n=in();m=in();
int i;
ln=index=0;
for(i=1;i<=n;i++){
type[i]=in();
if(!type[i])l[++ln]=i;
}
memset(a,0,sizeof(a));
memset(head,0,sizeof(head));
for(i=1;i<=m;i++){
int x,y;
x=in();y=in();
++x,++y;
if(type[x]!=type[y] && !a[x][y]){
a[x][y]=a[y][x]=1;
add(x,y);
add(y,x);
}
}
}
short lx[205],ly[205];
bool flag[205],del[205];
bool find(int x){
flag[x]=1;
for(node *p=head[x];p;p=p->next)
if(!flag[p->id] && !del[p->id]){
flag[p->id]=1;
if(!lx[p->id] || find(lx[p->id])){
lx[p->id]=x;
ly[x]=p->id;
return 1;
}
}
return 0;
}
bool dfs1(int x){
flag[x]=1;
for(node *p=head[x];p;p=p->next)
if(!flag[p->id] && !del[p->id]){
flag[p->id]=1;
if(!lx[p->id] || dfs1(lx[p->id]))
return 1;
}
return 0;
}
bool dfs2(int x){
flag[x]=1;
for(node *p=head[x];p;p=p->next)
if(!flag[p->id] && !del[p->id]){
flag[p->id]=1;
if(!ly[p->id] || dfs2(ly[p->id]))
return 1;
}
return 0;
}
int hungary(){
memset(lx,0,sizeof(lx));
memset(ly,0,sizeof(ly));
int i,ans=0;
for(i=1;i<=ln;i++)
if(!del[l[i]]){
memset(flag,0,sizeof(flag));
if(find(l[i]))ans++;
}
return ans;
}
void Sov(){
memset(del,0,sizeof(del));
int i,max=hungary();
out(max);
for(i=1;i<=n && max;i++){
if(!lx[i] && !ly[i])continue;
else if(lx[i]){
memset(flag,0,sizeof(flag));
del[i]=1;
if(!dfs1(lx[i])){
max--;
ly[lx[i]]=0;
putchar(' ');
out(i-1);
}
else
del[i]=0;
}
else if(ly[i]){
memset(flag,0,sizeof(flag));
del[i]=1;
if(!dfs2(ly[i])){
max--;
lx[ly[i]]=0;
putchar(' ');
out(i-1);
}
else
del[i]=0;
}
}
puts("");
}
int main(){
int t;
t=in();
while(t--){
Build_Graph();
Sov();
}
return 0;
}神一样的读入输出优化~~~
PS：图论的建图还是纠结，但是悲剧的是比赛的时候往往遇到稍微麻烦点的图论还没开始纠结比赛就已经over了，总是卡水题，悲剧啊