[網絡流24題] 最小路徑覆寫問題
★★☆ 輸入檔案：path3.in 輸出檔案：path3.out 評測插件
時間限制：1 s 記憶體限制：128 MB
算法實作題8-3 最小路徑覆寫問題（習題8-13）
´問題描述：
給定有向圖G=(V,E)。設P是G的一個簡單路（頂點不相交）的集合。如果V中每個
頂點恰好在P的一條路上，則稱P是G的一個路徑覆寫。P中路徑可以從V的任何一個頂
點開始，長度也是任意的，特别地，可以為0。G的最小路徑覆寫是G的所含路徑條數最少
的路徑覆寫。
設計一個有效算法求一個有向無環圖G的最小路徑覆寫。
提示：
設V={1，2，… ，n}，構造網絡G1=(V1,E1)如下：
每條邊的容量均為1。求網絡G1的(x0,y0)最大流。
´程式設計任務：
對于給定的給定有向無環圖G，程式設計找出G的一個最小路徑覆寫。
´資料輸入：
由檔案input.txt提供輸入資料。檔案第1行有2個正整數n和m。n是給定有向無環圖
G的頂點數，m是G的邊數。接下來的m行，每行有2個正整數i 和j，表示一條有向邊(i,j)。
´結果輸出:
程式運作結束時，将最小路徑覆寫輸出到檔案output.txt中。從第1行開始，每行輸出
一條路徑。檔案的最後一行是最少路徑數。
輸入檔案示例
input.txt
11 12
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 9
7 10
8 11
9 11
10 11
輸出檔案示例
output.txt
1 4 7 10 11
2 5 8
3 6 9
3
資料範圍：
1<=n<=150,1<=m<=6000
/*
最小路徑覆寫數=V-最大流.
然後拆點建圖.
搞一個超級源點和彙點跑dinic.
輸出的時候在殘餘網絡裡找貢獻邊.
恩就是這樣.
*/
#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define MAXN 10001
using namespace std;
struct data{int v,next,c;}e[MAXN*4];
int n,m,max1=e9,ans,tot,cut=,dis[MAXN*2],head[MAXN*2],next[MAXN*2];
bool in[MAXN*2];
inline int read()
{
int x=,f=;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-;ch=getchar();}
while(ch>='0'&&ch<='9') x=x*10+ch-,ch=getchar();
return x*f;
}
void add(int u,int v,int x)
{
e[++cut].v=v;
e[cut].c=x;
e[cut].next=head[u];
head[u]=cut;
}
bool bfs()
{
memset(dis,-,sizeof dis);
queue<int>q;
q.push();
dis[]=;
while(!q.empty())
{
int u=q.front();q.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(dis[v]==-&&e[i].c)
{
dis[v]=dis[u]+;
q.push(v);
}
}
}
return dis[n*2+]!=-;
}
int dfs(int u,int y)
{
if(u==n*2+) return y;
int rest=;
for(int i=head[u];i&&rest<y;i=e[i].next)
{
int v=e[i].v;
if(dis[v]==dis[u]+&&e[i].c)
{
int x=dfs(v,min(e[i].c,y-rest));
rest+=x;
e[i].c-=x;
e[i^].c+=x;
}
}
if(!rest) dis[u]=-;
return rest;
}
void print()
{
for(int u=;u<=n;u++)
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].v;
if(e[i].c==max1-) in[v-n]=true,next[u]=v-n;
}
for(int i=;i<=n;i++)
{
int x=i;
if(!in[x])
{
while(x) printf("%d ",x),x=next[x];
printf("\n");
}
}
}
void dinic(int s,int t)
{
while(bfs()) ans+=dfs(s,max1);
print();
printf("%d\n",n-ans);
return ;
}
int main()
{
freopen("path3.in","r",stdin);
freopen("path3.out","w",stdout);
int x,y;
n=read(),m=read();
for(int i=;i<=n;i++) add(,i,),add(i,,);
for(int i=;i<=n;i++) add(i+n,n*2+,),add(*n+,i+n,);
for(int i=;i<=m;i++)
{
x=read(),y=read();
add(x,y+n,max1),add(y+n,x,);
}
dinic(,n*2+);
return ;
}
轉載于:https://www.cnblogs.com/nancheng58/p/10068143.html