Description
假期，Hrbust集训队在Tang长老的带领下去河上坐船游玩。 但是很多队员想单独坐船游览风光，体验一个人的旅行。 但是教主说那样会很危险，而且似乎也没那么多的旅行路线。可是队员们还是坚持自己的想法，于是教主提了个要求：如果游览的路线足够一人一条，而且每条路线没有重复的水路的话，就同意大家的做法，不然，Tang长老就请大家集体吃冰棍，一起坐船去。
集训队这次一共去了 D 个人，（1<=D<=200），已知河道上一共N个河叉（2<=N<=200），大家都是从1号位置开始旅行的，终点为第 N 号位置，现在已知道在这N个位置之间有 M 条连通的水路(2<=M<=40000)。
请帮大家计算下存在的路线数是否够大家单人旅行的。
Input
Line 1: 河叉总数 N，道路总数 M，集训队人数 D。
Line 2…M+1:两个整数 A,B，表示位置 A 和 B 之间有一条直接连通的水路。
Output
Line1:如果存在的路径数够大家单人旅行(路径数>= D),输出“Orz!”,否则输出“Jiao Zhu v5!”。
Sample Input
2 2 1
1 2
1 2
7 9 5
1 2
2 3
3 7
1 4
4 3
4 5
5 7
1 6
6 7
Sample Output
Orz!
Jiao Zhu v5!
Hint
注意是边是双向的。
第一组样例：
从 1 到 2 有两条没有重复道路的路径。
第二组样例：
从 1 到 7 有三条符合条件的路径：
1 - 2 - 3 - 7
1 - 4 - 5 -7
1 - 6 - 7
最大流模板题，重边数量为一个节点到另一个节点的容量，直接求1到n的最大流量即可。建图时遇到一条重边就计数，最后每条边有多少条重边即可以走几个不同路线。也就是可走容量
#include<bits/stdc++.h>
using namespace std;
const int maxn=208;
const int inf=0x3f3f3f3f;
struct edge
{
int to,val,rev;
edge() {}
edge(int a,int b,int c)
{
to=a;
val=b;
rev=c;
}
};
int dep[maxn];
int n,m,d;
vector<edge>mp[maxn];
void add(int from,int to,int val)
{
mp[from].push_back(edge(to,val,mp[to].size()));
mp[to].push_back(edge(from,val,mp[from].size()-1));
}
int bfs()
{
memset(dep,-1,sizeof dep);
queue<int >q;
while(!q.empty())q.pop();
dep[1]=0;
q.push(1);
while(!q.empty())
{
int tmp=q.front();
q.pop();
if(tmp==n)return 1;
for(int i=0;i<mp[tmp].size();i++)
{
int &to=mp[tmp][i].to,flow=mp[tmp][i].val;
if(dep[to]==-1&&flow)
{
dep[to]=dep[tmp]+1;
q.push(to);
}
}
}
return 0;
}
int dfs(int s,int t,int flow)
{
if(s==t)return flow;
int pre=0;
for(int i=0;i<mp[s].size();i++)
{
int &to=mp[s][i].to,val=mp[s][i].val;
if(dep[s]+1==dep[to]&&val>0)
{
int tmp=min(flow-pre,val);
int sub=dfs(to,t,tmp);
mp[s][i].val-=sub;
mp[to][mp[s][i].rev].val+=sub;
pre+=sub;
if(pre==flow)return pre;
}
}
return pre;
}
int dinic()
{
int ans=0;
while(bfs())ans+=dfs(1,n,inf);
return ans;
}
map<int,int >vis;
int main()
{
while(scanf("%d%d%d",&n,&m,&d)!=EOF)
{
int from,to;
vis.clear();
for(int i=0; i<=n; i++)mp[i].clear();
for(int i=0; i<m; i++)
{
scanf("%d%d",&from,&to);
vis[from*300+to]++;///可能是因为数据水，这样加边方式足足加了4次边
}
map<int,int>::iterator it;
for(it=vis.begin(); it!=vis.end(); it++)
add(it->first/300,it->first%300,it->second);
printf("%s
",dinic()>=d?"Orz!":"Jiao Zhu v5!");
}
}