随笔-141  评论-9  文章-3  trackbacks-0

题意:二分图最大匹配问题。

解法1:匈牙利算法。

解法2:最大流。

添加原点s和汇点t。
设二分图左边的点集为X,添加从s 到X(1,2,....,m )的边,权值为1;
右边的点集为Y,添加从Y(n-m+1, n-m+1, .... , n)到t 的边,权值为1;
田间X和Y之间的边。

求最大流。我用Dinic。最大流就是最大匹配。 配对保存在flow[i][j]中。

#include <fstream>
#include 
<memory.h>

using namespace std;

const int MAX = 300;
const int INF = 0x7FFFFFFF;

class Tadj{
public:
    
int cnt;
    
int to[MAX];
    Tadj()
{
        cnt
=0;
    }

    
void ins(int k){
        to[
++cnt]=k;
    }

}
;

class Tqueue{
private:
    
long first, last, size;
    
long list[MAX*MAX];
public:
    Tqueue()
{
        reset();
    }


    
void reset(){
        first
=1, last=0, size=0;
    }


    
void push_back(int k){
        
++size;
        list[
++last]=k;
    }


    
void pop_front(){
        size
--;
        first
++;
    }


    
long front(){
        
return list[first];
    }


    
bool empty(){
        
return size==0;
    }

}
;

class Tstack{
public:
    
int stack[MAX];
    
int top, min, p;

    Tstack()
{
        reset();
    }


    
void reset(){
        top
=0, min=INF;
    }


    
void pop(){
        top
--;
    }


    
void push(int k){
        stack[
++top]=k;
    }

}
;

ifstream fin(
"input.txt");
ofstream fout(
"output.txt");

Tqueue Q;
Tstack S;
Tadj adj[MAX];

int s,t,c1,c2,m,n,maxflow;
int level[MAX], set[MAX];
int dist[MAX][MAX], odist[MAX][MAX], flow[MAX][MAX];
bool used[MAX];

inline 
void insert(int u, int v, int cost){
    adj[u].ins(v);
    dist[u][v]
=cost;
}


void input(){
    
int i,u,v;
    fin
>>m>>n;

    s
=0, t=n+1;

    
for(i=1; i<=m; ++i){
        insert(s, i, 
1);
        insert(i, s, 
0);
    }


    
for(i=n-m+1; i<=n; ++i){
        insert(i, t, 
1);
        insert(t, 
10);
    }


    fin
>>u>>v;
    
while(u!=-1 && v!=-1){
        insert(u, v, 
1);
        insert(v, u, 
0);
        fin
>>u>>v;
    }


    adj[t].cnt
=0;
    memcpy(odist, dist, 
sizeof(dist));
}


void Dinic_Level(){
    Q.reset();
    memset(used, 
0sizeof(used));
    memset(level, 
0sizeof(level));
    Q.push_back(s);
    
while(!Q.empty()){
        
int u = Q.front();
        Q.pop_front();
        used[u]
=true;
        
for(int i=1; i<=adj[u].cnt; ++i){
            
int v = adj[u].to[i];
            
if(!dist[u][v])    continue;
            
if(used[v] || v==s) continue;
            level[v] 
= level[u]+1;
            Q.push_back(v);
        }

    }

}


void Dinic_Argument(){
    S.stack[
0]=s;
    
for(int i=1; i<=S.top; ++i){
        
int u = S.stack[i-1];
        
int v = S.stack[i];
        
if(dist[u][v]<S.min){
            S.min 
= dist[u][v];
            S.p   
= u; 
        }

    }


    
for(int j=S.top; j>=1--j){
        
int u = S.stack[j-1];
        
int v = S.stack[j];
        flow[u][v] 
+= S.min;
        dist[u][v] 
-= S.min;
        dist[v][u] 
+= S.min;
    }

}


bool Dinic_dfs(int u){
    
int outdegree=0;
    
if(u!=t){
        
for(int i=1; i<=adj[u].cnt; ++i){
            
int v = adj[u].to[i];
            
if(level[v]==level[u]+1 && dist[u][v]){
                outdegree
++;
                S.push(v);
                
bool f = Dinic_dfs(v);
                S.pop();
                
if(f && u!=S.p)
                    
return true;
            }
    
        }

        
if(outdegree==0)
            level[u]
=0;
    }
else{
        Dinic_Argument();
        
return true;
    }

    
return false;
}


void Dinic(){
    memset(flow, 
0sizeof(flow));
    
for( ; ; ){
        Dinic_Level();
        
if(level[t]==0)
            
return;
        S.reset();
        Dinic_dfs(s);
    }

}


long max_flow(){
    
long ret = 0;
    
for(int i=1; i<=n*2++i)
        ret 
+= flow[s][i];
    
return ret;
}


void solve(){
    
int cnt = 0;
    Dinic();
    maxflow 
= max_flow();
}


void output(){
    fout
<<maxflow<<endl;
    
for(int i=1; i<=m; ++i)
        
for(int j=n-m+1; j<=n; ++j){
            
if(flow[i][j]==1)
                fout
<<i<<" "<<j<<endl;
        }

}


int main(){

    input();

    solve();

    output();

    
return 0;
}



 

posted on 2011-02-24 12:35 小阮 阅读(750) 评论(0)  编辑 收藏 引用 所属分类: 数据结构和算法

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