(http://www.elijahqi.win/2017/12/15/loj-6002-%E3%80%8C%E7%BD%91%E7%BB%9C%E6%B5%81-24-%E9%A2%98%E3%80%8D%E6%9C%80%E5%B0%8F%E8%B7%AF%E5%BE%84%E8%A6%86%E7%9B%96/%20%E2%80%8E)
題目描述
«問題描述：
給定有向圖G=(V,E)。設P 是G 的一個簡單路（頂點不相交）的集合。如果V 中每個頂點恰好在P 的一條路上，則稱P是G 的一個路徑覆寫。P 中路徑可以從V 的任何一個頂點開始，長度也是任意的，特别地，可以為0。G 的最小路徑覆寫是G 的所含路徑條數最少的路徑覆寫。設計一個有效算法求一個有向無環圖G 的最小路徑覆寫。提示：設V={1，2，…. ，n}，構造網絡G1=(V1,E1)如下：
每條邊的容量均為1。求網絡G1的（ 0 x , 0 y ）最大流。
«程式設計任務：
對于給定的給定有向無環圖G，程式設計找出G的一個最小路徑覆寫。
輸入輸出格式
輸入格式：
件第1 行有2個正整數n和m。n是給定有向無環圖G 的頂點數，m是G 的邊數。接下來的m行，每行有2 個正整數i和j，表示一條有向邊(i,j)。
輸出格式：
從第1 行開始，每行輸出一條路徑。檔案的最後一行是最少路徑數。
輸入輸出樣例
輸入樣例#1： 複制
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
輸出樣例#1： 複制
1 4 7 10 11
2 5 8
3 6 9
3
說明
1<=n<=150,1<=m<=6000
由@zhouyonglong提供SPJ
首先建圖 然後從源點向每個節點的入點都連權值為1的邊 從每個點的出點都向彙點連權值為1的邊 然後如果這兩點之間原來有邊那麼從起點的出點向終點的入點連1的邊 跑dinic完成最大比對 那麼最後答案就是節點數-最大比對數
#include<queue>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define N 400
inline char gc(){
static char now[1<<16],*S,*T;
if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;}
return *S++;
}
inline int read(){
int x=0;char ch=gc();
while(ch<'0'||ch>'9') ch=gc();
while(ch<='9'&&ch>='0'){x=x*10+ch-'0';ch=gc();}
return x;
}
struct node{
int y,next,z;
}data[15000];
int num=1,h[N],T,level[N],n,m;
bool visit[N];
inline void insert1(int x,int y,int z){
data[++num].y=y;data[num].next=h[x];h[x]=num;data[num].z=z;
data[++num].y=x;data[num].next=h[y];h[y]=num;data[num].z=0;
}
inline bool bfs(){
queue<int> q;q.push(0);memset(level,0,sizeof(level));level[0]=1;
while(!q.empty()){
int x=q.front();q.pop();
for (int i=h[x];i;i=data[i].next){
int y=data[i].y,z=data[i].z;
if (level[y]||!z) continue;level[y]=level[x]+1;q.push(y);if(y==T) return 1;
}
}return 0;
}
inline int dfs(int x,int s){
if (x==T) return s;int ss=s;
for (int i=h[x];i;i=data[i].next){
int y=data[i].y,z=data[i].z;
if (level[y]==level[x]+1&&z){
int xx=dfs(y,min(z,s));if (!xx) level[y]=0;
s-=xx;data[i].z-=xx;data[i^1].z+=xx;if (!s) return ss;
}
}return ss-s;
}
int main(){
freopen("loj.in","r",stdin);
freopen("loj.out","w",stdout);
n=read();m=read();T=n*2+1;
for (int i=1;i<=n;++i) insert1(0,i,1),insert1(i+n,T,1);
for (int i=1;i<=m;++i){int x=read(),y=read();insert1(x,y+n,1);}int ans=0;
while(bfs()) ans+=dfs(0,inf);
for (int i=1;i<=n;++i){
if (visit[i]) continue;int now=i;bool flag=0;
do{
printf("%d ",now);visit[now]=1;flag=0;
for (int i=h[now];i;i=data[i].next)
if (!data[i].z&&data[i].y>n&&data[i].y<=2*n){now=data[i].y-n;flag=1;break;}
}while(flag);puts("");
}
printf("%d",n-ans);
return 0;
}