【问题描述】
小火车的 ddl 赶不完了， 他不愿意也没时间去思考题目背景到底应该怎么写了。
有一张 n 个点 m 条边的有向无环图，k 个人同时想从1号点走到 n号点，每个人每个时刻都会沿着一条边走过去，不能不走（除非他们已经到达了n号点），不过每条边每个时刻都只能有一个人经过，请问他们中最晚的人最早什么时候能到 n号点呢？如果不可能的话输出-1。
【输入格式】
第一行三个整数n,m,k，含义如题所述。
接下来m行每行两个整数u和v表示一条边。保证不存在自环，但可能有重边。
【输出格式】
一行一个整数表示答案。
【样例输入输出】
输入
8 11 3
1 2
1 3
1 4
6 7
2 5
3 6
3 2
4 6
5 7
7 8
2 7
输出：
5
【数据范围与约定】
对于 20%的数据 n<=20， k<=4；
对于 50%的数据 n<=50, m, k<=200；
对于 100%的数据 n<=100, m, k<=1000；
分析：网络流
建图有点类似“家园”
第1层点是n个散点，每次连边就加一层，
每条边都是从上一层连到当前层，表示时间的推移
每一层的n点都连向下层，因为人们可以在n点停留
为什么其他点不用呢，因为人们不能在路上停留（~注意读题）
这道题是有历史意义的，第一次使用当前弧优化（原来这么好用~~~）
当前弧优化主要体现在以下三个点：
bfs中：
for (int i=s;i<=t;i++) cur[i]=st[i]; dfs中：
for (i=cur[now];i!=-1;i=way[i].nxt)
cur[now]=i; ///弧优化的原理就是：
每次我们进行增广时，都是完全增广，那就存在一些边无法增广（无论怎样都不行），那下一次dfs时我们就不需要再遍历这些边了，所以我们新开一个数组cur，记录上次搜索到的边
这里写代码片
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=500001;
const int INF=0x33333333;
int n,m,k;
struct node{
int x,y,v,nxt;
};
node way[N];
int st[N],tot=-1,s,t,deep[N];
int bian[1010][2];
int cur[N]; //历史性的一天，当前弧优化
bool p[N];
void add(int u,int w,int z)
{
tot++;
way[tot].x=u;way[tot].y=w;way[tot].v=z;way[tot].nxt=st[u];st[u]=tot;
tot++;
way[tot].x=w;way[tot].y=u;way[tot].v=0;way[tot].nxt=st[w];st[w]=tot;
return;
}
void lianbian1()
{
int i,j;
for (i=1;i<n;i++)
{
//n向下层连
add(n+(i-1)*n,n+(i*n),INF);
for (j=1;j<=m;j++)
{
int f1=bian[j][0];
int f2=bian[j][1];
add(f1+(i-1)*n,f2+i*n,1); //向下层连边
}
}
s=1; t=n*n;
return;
}
/*
讲真连边连得我很方，第0层点是n个散点，每次连边就加一层，
每条边都是从上一层连到当前，表示时间的推移
每一层的n点都连向下层，因为人们可以在n点停留
为什么其他点不用呢，因为人们不能在路上停留
*/
void lianbian2(int ce)
{
int i,j;
t=ce*n;
add(n+(ce-1)*n,n+ce*n,INF);
for (j=1;j<=m;j++)
{
int f1=bian[j][0];
int f2=bian[j][1];
add(f1+(ce-1)*n,f2+ce*n,1); //向下层连边
}
return;
}
int bfs()
{
queue<int> q;
memset(deep,0x33,sizeof(deep));
memset(p,1,sizeof(p));
q.push(s);
p[s]=0;
deep[s]=1;
for (int i=s;i<=t;i++) cur[i]=st[i];
while (!q.empty())
{
int r=q.front();
q.pop();
for (int i=st[r];i!=-1;i=way[i].nxt)
{
if (way[i].v&&p[way[i].y])
{
deep[way[i].y]=deep[r]+1;
p[way[i].y]=0;
q.push(way[i].y);
}
}
}
return !p[t];
}
int dfs(int now,int t,int limit)
{
if (!limit||now==t) return limit;
int i,f,flow=0;
for (i=cur[now];i!=-1;i=way[i].nxt) //cur
{
cur[now]=i; ///
if (deep[way[i].y]==deep[now]+1&&way[i].v&&(f=dfs(way[i].y,t,min(limit,way[i].v))))
{
flow+=f;
limit-=f;
way[i].v-=f;
way[i^1].v+=f;
if (!limit) break;
}
}
return flow;
}
void solve()
{
int ans=0,i;
s=1;
for (i=1;i;i++)
{
lianbian2(i);
while (bfs())
ans+=dfs(s,t,INF);
if (ans>=k) break;
}
printf("%d",i-1); //为什么要-1，我也不知道啊，对着样例调一调就好啦
}
int doit()
{
int ans=0;
while (bfs())
ans+=dfs(s,t,INF);
if (ans>=k) return 1;
else return 0;
}
int main()
{
//freopen("san.in","r",stdin);
//freopen("san.out","w",stdout);
memset(st,-1,sizeof(st));
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=m;i++)
{
int u,w;
scanf("%d%d",&bian[i][0],&bian[i][1]);
}
lianbian1();
if (doit()==0)
{
printf("-1");
}
else
{
memset(way,0,sizeof(way));
memset(st,-1,sizeof(st));
tot=-1; s=t=0;
solve();
}
return 0;
}