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

题意:
有向无环图中,需要多少条简单路可以覆盖整个图。

建模:
构造二分图。把原图的每个顶点i拆分成二分图X,Y集合中的两个顶点Xi和Yi。对于原图的边(i, i),连接(Xi, Yj),值为1,然后把二分图最大匹配模型转化为网络留模型,求最大流。

分析:

对于一个路径覆盖,有如下性质:

1、每个顶点属于且只属于一个路径。
2、路径上除终点外,从每个顶点出发只有一条边指向路径上的另一顶点。

所以我们可以把每个顶点理解成两个顶点,一个是出发,一个是目标,建立二分图模型。该二分图的任何一个匹配方案,都对应了一个路径覆盖方案。如果匹配数为0,那么显然路径数=顶点数。每增加一条匹配边,那么路径覆盖数就减少一个,所以路径数=顶点数 - 匹配数。要想使路径数最少,则应最大化匹配数,所以要求二分图的最大匹配。

注意,此建模方法求最小路径覆盖仅适用于有向无环图,如果有环或是无向图,那么有可能求出的一些环覆盖,而不是路径覆盖。


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

using namespace std;

const int MAXN = 100;
const int MAXM = MAXN*MAXN;
const int INF  = 0x7FFFFFF;

typedef 
struct edge{
    edge 
*next, *op;
    
int t,c;
}
edge;

edge ES[MAXM], 
*V[MAXN], *P[MAXN], *Stae[MAXN];
int level[MAXN], Stap[MAXN];
int M, N, S, T, EC, Ans, Maxflow;

ifstream fin(
"path.in");
ofstream fout(
"path.out");

inline 
void addedge(int a, int b, int c){
    ES[
++EC].next=V[a], V[a]=ES+EC, V[a]->t=b, V[a]->c=c;
    ES[
++EC].next=V[b], V[b]=ES+EC, V[b]->t=a, V[b]->c=0;
    V[a]
->op=V[b], V[b]->op=V[a];
}


bool Dinic_Level(){
    
int head,tail,i,j;
    Stap[head
=tail=0]=S;
    memset(level,
-1,sizeof(level));
    level[S]
=0;
    
while (head<=tail){
        i
=Stap[head++];
        
for (edge *e=V[i];e;e=e->next){
            j
=e->t;
            
if (e->&& level[j]==-1){
                level[j] 
= level[i]+1;
                
if (j==T)
                    
return true;
                Stap[
++tail] = j;
            }

        }

    }

    
return false;
}


int match[MAXN+MAXN];
void Dinic_Augment(){
    
int i,j,delta,Stop;

    memcpy(P, V, 
sizeof(edge*)*MAXN);

    Stap[Stop
=1]=S;
    
while (Stop){
        i
=Stap[Stop];
        
if (i!=T){
            
for (;P[i];P[i]=P[i]->next)
                
if (P[i]->&& level[i] + 1 == level[j=P[i]->t])
                    
break;
            
if (P[i]){
                Stap[
++Stop] = j;
                Stae[Stop] 
= P[i];
            }
else
                Stop
--,level[i]=-1;
        }
else{
            delta 
= INF;
            
for (i=Stop;i>=2;i--)
                
if (Stae[i]->< delta)
                    delta 
= Stae[i]->c;
            Maxflow 
+= delta;
            
for (i=Stop;i>=2;i--){
                Stae[i]
->-= delta;
                Stae[i]
->op->+= delta;
                
if (Stae[i]->c==0)
                    Stop 
= i-1;
            }

            match[Stae[
2]->t] = Stae[3]->t;
        }

    }

}


void Dinic(){
    
while (Dinic_Level())
        Dinic_Augment();
}


void input(){
    
int a,b,i;
    fin
>>N>>M;
    S
=0, T=N+N+1;
    
for(i=1; i<=N; ++i){
        addedge(S, 
2*i-1,1);
        addedge(
2*i, T, 1);
    }


    
for(i=1; i<=M; ++i){
        fin
>>a>>b;
        addedge(
2*a-12*b, INF);
    }

}


bool visited[MAXN];
void dfs(int k){
    fout
<<(k+1)/2<<" ";
    
if(match[k]&&!visited[k]){
        visited[k]
=true;
        dfs(match[k]
-1);
    }

}


void output(){
    
int c = N+N;
    
for(int i=1; i<c; i+=2){
        
if(match[i]&&!visited[i]){
            dfs(i);
            fout
<<endl;
        }

    }

    fout
<<N-Maxflow<<endl;
}


int main(){
    input();
    Dinic();
    output();
    
return 0;
}
posted on 2011-03-05 23:29 小阮 阅读(1740) 评论(0)  编辑 收藏 引用 所属分类: 数据结构和算法

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