fork(2) download
copy 
  1. #include <stdio.h>
  2. #include <iostream>
  3. #include <memory.h>
  4. #include <algorithm>
  5. #include <queue>
  6. #include <vector>
  7. #include <map>
  8. #include <math.h>
  9. #include <stack>
  10. #include <limits.h>
  11. #include <iomanip>
  12.  
  13. using namespace std;
  14. #define zero(x) memset(x,0,sizeof(x))
  15. #define mone(x) memset(x,-1,sizeof(x))
  16. #define ll long long
  17. #define base 31
  18. #define mod 1000000007
  19. #define X first
  20. #define Y second
  21. #define fo(i,n) for(i=0;i<n;i++)
  22. #define foo(i,n) for(i=1;i<=n;i++)
  23. #define fa(i,I,n) for(i=I;i<n;i++)
  24. #define sz(x) x.size()
  25. #define pb push_back
  26. const int inf=(1<<28);
  27. int n,m,i,j,k,l,t,K;
  28. namespace max_flow{
  29.     const int M=300,oo=(1<<28);
  30.     vector<int>g[M];
  31.     //p[i][j] capacidad de la arista (i,j)
  32.     //r[i][j] camino recidual
  33.     int r[M][M],p[M][M],path[M];
  34.     bool mar[M];
  35.     void init(){
  36.         zero(p);
  37.         for(int i=0;i<M;i++)g[i].clear();
  38.     }
  39.     void add(int a,int b,int v){
  40.         g[a].push_back(b);
  41.         p[a][b]=v;
  42.     }
  43.     int bfs(int no,int nof){
  44.         queue<int>q,q2;
  45.         q.push(no);q2.push(oo);
  46.         zero(mar);zero(path);
  47.         mar[no]=1;
  48.         path[nof]=path[no]=-1;
  49.         while(!q.empty()){
  50.             int nn=q.front(),pp=q2.front(),i;
  51.             q.pop();q2.pop();
  52.             fo(i,sz(g[nn])){
  53.                 int hi=g[nn][i],cc=p[nn][hi]-r[nn][hi];
  54.                 if(cc>0&&!mar[hi]){
  55.                     mar[hi]=1;
  56.                     path[hi]=nn;
  57.                     if(hi==nof)return min(pp,cc);
  58.                     q.push(hi);q2.push(min(pp,cc));
  59.                 }
  60.             }
  61.         }
  62.         return 0;
  63.     }
  64.     int flow(int ini,int fin){
  65.         int sol=0,val,po;zero(r);
  66.         while(val=bfs(ini,fin)){
  67.             sol+=val;
  68.             po=fin;
  69.             while(path[po]!=-1){
  70.                 r[path[po]][po]+=val;
  71.                 r[po][path[po]]-=val;
  72.                 po=path[po];
  73.             }
  74.         }
  75.         return sol;
  76.     }
  77. }
  78. int graph[55][55],paths[4005][2];
  79. int main(){
  80.     while(1){
  81.         scanf("%d%d%d",&n,&m,&K);
  82.         if(n+m+K==0)break;
  83.         max_flow::init();
  84.         fo(i,n)fo(j,n)graph[i][j]=(i==j?0:inf);//init floy
  85.         fo(i,m){
  86.             int u,v;
  87.             scanf("%d%d",&u,&v);u--;v--;
  88.             paths[i][0]=u;
  89.             paths[i][1]=v;
  90.             graph[u][v]=1;
  91.         }
  92.         fo(k,n)fo(i,n)fo(j,n)//floy
  93.             graph[i][j]=min(graph[i][k]+graph[k][j],graph[i][j]);
  94.         fo(i,n){
  95.             max_flow::add(i,i+n,(i>0&&i<n-1?1:inf));
  96.             max_flow::add(i+n,i,0);
  97.         }
  98.         fo(i,m){
  99.             int u=paths[i][0],v=paths[i][1];
  100.             if(u==v)continue;
  101.             if(graph[0][u]+1+graph[v][n-1]<=K){
  102.                 max_flow::add(u+n,v,1);
  103.                 max_flow::add(v,u+n,0);
  104.             }
  105.         }
  106.         printf("%d\n",max_flow::flow(0,n-1));
  107.     }
  108.     return 0;
  109. }
Success #stdin #stdout 0s 3988KB
comments (?)
stdin
copy 
5 7 6
1 2
1 3
3 2
3 4
4 3
4 5
2 5
7 10 6
1 2
1 3
2 4
3 4
4 5
4 6
5 7
6 7
6 4
5 4
0 0 0
stdout
copy 
2
1
https://ideone.com/blJfSK
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!