题意:
有向无环图中,需要多少条简单路可以覆盖整个图。
建模:
构造二分图。把原图的每个顶点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->c && 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]->c && 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]->c < delta)
delta = Stae[i]->c;
Maxflow += delta;
for (i=Stop;i>=2;i--){
Stae[i]->c -= delta;
Stae[i]->op->c += 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-1, 2*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
小阮 阅读(1764)
评论(0) 编辑 收藏 引用 所属分类:
数据结构和算法