Posted on 2010-08-08 19:34
Uriel 閱讀(427)
評論(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了，總是卡水題，悲劇啊