好久没有更新博客了啊……屯了一堆题没发呢
这是丧心病狂的hzwer每日NOI模拟赛第一天的第一题
妈蛋说好的NOIP难度图论算法两题网络流！让我说什么好
唔……codecomb的页面在晚上就会变得很奇怪
题目描述
给定一张n个点的有向图，求从点1到点n最多有多少条不相交的简单路径。所谓不相交即不经过相同的边的路径。
输入格式
第一行读入一个n，m，表示共n个点，m条边。
接下来m行，每行两个整数x，y，表示从x到y有一条有向边。
输出格式
输出仅包括一行，即最多有多少条不相交的简单路劲。
样例数据 1
备注
对于20%的数据n<=10，m<=1000；
对于100%的数据n<=1000，m<=100000；
一看就是sb无脑网络流了……十分钟打完还算快
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<deque>
#include<set>
#include<map>
#include<ctime>
#define LL long long
#define inf 0x7ffffff
#define pa pair<int,int>
#define pi 3.1415926535897932384626433832795028841971
#define S 1
#define T n
using namespace std;
struct edge{
int to,next,v;
}e[200010];
int head[10010];
int n,m,cnt=1,t,w,ans;
int h[10010];
int q[100010];
inline void ins(int u,int v,int w)
{
e[++cnt].to=v;
e[cnt].v=w;
e[cnt].next=head[u];
head[u]=cnt;
}
inline void insert(int u,int v,int w)
{
ins(u,v,w);
ins(v,u,0);
}
inline bool bfs()
{
memset(h,-1,sizeof(h));
t=0;w=1;h[S]=0;q[1]=S;
while (t<w)
{
int now=q[++t];
for(int i=head[now];i;i=e[i].next)
if (e[i].v&&h[e[i].to]==-1)
{
h[e[i].to]=h[now]+1;
q[++w]=e[i].to;
}
}
if (h[T]==-1)return 0;
return 1;
}
inline int dfs(int x,int f)
{
if (x==T||!f)return f;
int used=0,w;
for (int i=head[x];i;i=e[i].next)
if (e[i].v&&h[e[i].to]==h[x]+1)
{
w=used;
w=dfs(e[i].to,min(e[i].v,f-w));
e[i].v-=w;
e[i^1].v+=w;
used+=w;
if (!f)return used;
}
if (!used)h[x]=-1;
return used;
}
inline void dinic()
{
while (bfs())ans+=dfs(S,inf);
}
inline LL read()
{
LL 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 main()
{
n=read();m=read();
for (int i=1;i<=m;i++)
{
int x=read(),y=read();
insert(x,y,1);
}
dinic();
printf("%d\n",ans);
}