「codecomb2091」路径数量
题目描述
给定一张n个点的有向图，求从点1到点n最多有多少条不相交的简单路径。所谓不相交即不经过相同的边的路径。
输入格式
第一行读入一个n，m，表示共n个点，m条边。
接下来m行，每行两个整数x，y，表示从x到y有一条有向边。
输出格式
输出仅包括一行，即最多有多少条不相交的简单路劲。
样例数据 1
输入
4 7
1 2
1 2
2 3
2 3
2 3
3 4
3 4
输出
2
备注
对于20%的数据n<=10，m<=1000；
对于100%的数据n<=1000，m<=100000；
题解
网络流水过
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define inf 1000000000 #define ll long long using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt=1,ans; struct edge{int to,next,v;}e[200005]; int h[1005],last[1005],q[1005]; bool vis[1005]; void insert(int u,int v) { e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=1; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0; } bool bfs() { int head=0,tail=1; for(int i=1;i<=n;i++)h[i]=-1; q[0]=1;h[1]=0; while(head!=tail) { int now=q[head];head++; for(int i=last[now];i;i=e[i].next) if(e[i].v&&h[e[i].to]==-1) { h[e[i].to]=h[now]+1; q[tail++]=e[i].to; } } return h[n]!=-1; } int dfs(int x,int f) { if(x==n)return f; int w,used=0; for(int i=last[x];i;i=e[i].next) if(h[e[i].to]==h[x]+1) { w=f-used; w=dfs(e[i].to,min(e[i].v,w)); e[i].v-=w;e[i^1].v+=w; used+=w;if(used==f)return f; } if(!used)h[x]=-1; return used; } void dinic() { while(bfs())ans+=dfs(1,inf); } int main() { n=read();m=read(); for(int i=1;i<=m;i++) { int u=read(),v=read(); insert(u,v); } dinic(); printf("%d",ans); return 0; } |
Subscribe
计数器 9856754
OI 课件=>
OI 课件=>