Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594

POJ 3715 Blue and Red---二分图匹配

Posted on 2010-08-08 19:34 Uriel 阅读(382) 评论(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<=&& 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了,总是卡水题,悲剧啊

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理