Stikked

Untitled

From 上下界, 3 Years ago, written in Plain Text, viewed 2'572 times.
URL http://axuhongbo.top/paste/view/7fbf86cd Embed
Download Paste or View Raw
  1. #include<bits/stdc++.h>
  2. #define ms(x) memset(x,0,sizeof(x))
  3. using namespace std;
  4. const int inf = 1000000000;
  5. const int maxn = 104100;
  6. const int maxm = 108100;
  7. struct Edge
  8. {
  9.     int v, f, nxt;
  10. };
  11. int src, sink;
  12. int g[maxn + 10];
  13. int nume;
  14. int l, r;
  15. int n, m, k, step = 0;
  16. Edge e[maxm * 2 + 10];
  17. void addedge(int u, int v, int c)
  18. {
  19.     e[++nume].v = v;
  20.     e[nume].f = c;
  21.     e[nume].nxt = g[u];
  22.     g[u] = nume;
  23.     e[++nume].v = u;
  24.     e[nume].f = 0;
  25.     e[nume].nxt = g[v];
  26.     g[v] = nume;
  27. }
  28. void init()
  29. {
  30.     ms(g);
  31.     nume = 1;
  32. }
  33. int x, y;
  34. queue<int>que;
  35. bool vis[maxn+10];
  36. int dist[maxn+10];
  37. void bfs()
  38. {
  39.     ms(dist);
  40.     while(!que.empty()) que.pop();
  41.     vis[src] = true;
  42.     que.push(src);
  43.     while(!que.empty())
  44.     {
  45.         int u = que.front();
  46.         que.pop();
  47.         for(int i=g[u]; i; i=e[i].nxt)
  48.         {
  49.             if(e[i].f && !vis[e[i].v])
  50.             {
  51.                 que.push(e[i].v);
  52.                 dist[e[i].v] = dist[u] + 1;
  53.                 vis[e[i].v] = true;
  54.             }
  55.         }
  56.     }
  57. }
  58. int dfs(int u, int delta)
  59. {
  60.     if(u == sink)
  61.     {
  62.         return delta;
  63.     }
  64.     else
  65.     {
  66.         int ret = 0;
  67.         for(int i=g[u]; delta && i; i = e[i].nxt)
  68.         {
  69.             if(e[i].f && dist[e[i].v] == dist[u] + 1)
  70.             {
  71.                 int dd = dfs(e[i].v, min(e[i].f, delta));
  72.                 e[i].f -= dd;
  73.                 e[i^1].f += dd;
  74.                 delta -= dd;
  75.                 ret += dd;
  76.             }
  77.         }
  78.         return ret;
  79.     }
  80. }
  81. int maxflow()
  82. {
  83.     int ret = 0;
  84.     while(true)
  85.     {
  86.         ms(vis);
  87.         bfs();
  88.         if(!vis[sink]) return ret;
  89.         ret += dfs(src, inf);
  90.     }
  91. }
  92. int nn,mm;
  93. bool lowbound_flow()
  94. {
  95.     init();
  96.     int s  =n+m+1,t = n+m+2;
  97.     for(int i=0; i<k; i++)
  98.     {
  99.  
  100.         scanf("%d%d",&x,&y);
  101.         addedge(x,n+y,r-l);
  102.  
  103.     }
  104.     addedge(t,s,inf);
  105.     int S = n+m+3,T = n+m+4;
  106.     for(int i=1; i<=n; i++)
  107.     {
  108.         //addedge(s,i,r-l);
  109.         addedge(S,i,l);
  110.         addedge(i,T,l);
  111.     }
  112.     for(int i=1; i<=m; i++)
  113.     {
  114.         //addedge(n+i,t,r-l);
  115.         addedge(S,i,l);
  116.         addedge(n+i,T,l);
  117.     }
  118.     src = S;
  119.     sink = T;
  120.     int ans = maxflow();
  121.     if(ans == l*(n+m) )
  122.         return 1;
  123.     else return 0;
  124. }
  125. vector<int>u, v, L, U;
  126. int main()
  127. {
  128.  
  129.     while(scanf("%d%d%d",&n,&m,&k)!=EOF)
  130.     {
  131.  
  132.         scanf("%d%d",&l,&r);
  133.         printf("Case %d: ",++step);
  134.         if(lowbound_flow()) puts("Yes");
  135.         else puts("No");
  136.     }
  137.     return 0;
  138. }
  139.  

Replies to Untitled rss

Title Name Language When
nfmtnmXXVnJRA Merziuz text 11 Months ago.
Re: Untitled irvlkhzl text 1 Year ago.
Re: Untitled afuntyfe text 1 Year ago.
Re: Untitled bwyttwom text 1 Year ago.
Re: Untitled fhapglai text 1 Year ago.
Miracle eagle eye box usb driver Sole Wolf text 2 Years ago.
Rt3290 c2 драйвера Corrupt Cat text 2 Years ago.
Los lobos gipsy kings - la bamba mp3 free downloa Denim Zebra text 2 Years ago.
Halo 2 pc rar download Tiny Pig text 2 Years ago.
Manual del usuario lavarropas whirlpool wfe61a Trivial Human text 2 Years ago.
Test dpc 308 apk Abrupt Camel text 3 Years ago.
Maxqda license crack Eratic Madrill text 3 Years ago.
Dishonored русская озвучка 1с Round Wolf text 3 Years ago.
Mgmt discography 320kbps torrent Social Camel text 3 Years ago.
Le secret rhonda byrne dvdrip french torrent Gentle Bison text 3 Years ago.
123456

Reply to "Untitled"

Here you can reply to the paste above

captcha
Powered by Stikked