Advertisement
Guest User

Untitled

a guest
Aug 22nd, 2011
229
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.31 KB | None | 0 0
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<string.h>
  4. #include<vector>
  5. #include<queue>
  6. #include<map>
  7. #define pb push_back
  8. #define ppb pop_back
  9. #define mp make_pair
  10. #define all(x) (x).begin(),(x).end()
  11. #define sqr(x) (x) * (x)
  12. using namespace std;
  13. typedef pair<int, int> pii;
  14. struct edge
  15. {
  16.     int from;
  17.     int to;
  18.     int c;
  19.     int f;
  20.     edge *rev;
  21.     edge() : from(-1), to(-1), c(0), f(0), rev(NULL) {}
  22.     edge(int from, int to, int c, int f, edge *rev) : from(from), to(to), c(c), f(f), rev(rev) {}
  23. };
  24. const int INF = 1000000000;
  25. int used[22];
  26. vector<edge*> p(22);
  27. vector< vector<edge> > g(22);
  28. void addEdge(int from, int to, int cnt)
  29. {
  30.     g[from].pb(edge(from,to,cnt,0,NULL));
  31.     g[to].pb(edge(to,from,0,0,NULL));
  32.     g[from].back().rev = &g[to].back();
  33.     g[to].back().rev = &g[from].back();
  34. }
  35. int main()
  36. {
  37.     freopen("raceclass.in","r",stdin);
  38.     freopen("raceclass.out","w",stdout);
  39.     map<string, int> mp;
  40.     int n,m,k,s,t,cnt;
  41.     cin>>n>>m;
  42.     s = n + m;
  43.     t = n + m + 1;
  44.     vector<string> a(n),b(m);
  45.     string str,str1,str2;
  46.     for(int i = 0; i < n; i++)
  47.     {
  48.         cin>>cnt;
  49.         getline(cin,str);
  50.         str.erase(0,1);
  51.         a[i] = str;
  52.         mp[str] = i;
  53.         addEdge(s,i,cnt);
  54.     }
  55.     for(int i = 0; i < m; i++)
  56.     {
  57.         cin>>cnt;
  58.         getline(cin,str);
  59.         str.erase(0,1);
  60.         b[i] = str;
  61.         mp[str] = i + n;
  62.         addEdge(i + n,t,cnt);
  63.     }
  64.     cin>>k;
  65.     getline(cin,str);
  66.     for(int i = 0; i < k; i++)
  67.     {
  68.         getline(cin,str);
  69.         size_t pos = str.find("/");
  70.         str1 = str.substr(0,pos);
  71.         str.erase(0,pos + 1);
  72.         str2 = str;
  73.         addEdge(mp[str1],mp[str2],INF);
  74.     }
  75.     cout<<1<<endl;
  76.     queue<int> q;
  77.     while(true)
  78.     {
  79.         memset(used,0,sizeof(used));
  80.         used[s] = 1;
  81.         p[s] = NULL;
  82.         q.push(s);
  83.         while(!q.empty())
  84.         {
  85.             int from = q.front();
  86.             q.pop();
  87.             for(size_t i = 0; i < g[from].size(); i++)
  88.                 if (!used[g[from][i].to] && g[from][i].c - g[from][i].f > 0)
  89.                 {
  90.                     p[g[from][i].to] = &g[from][i];
  91.                     used[g[from][i].to] = 1;
  92.                     q.push(g[from][i].to);
  93.                 }
  94.         }
  95.         if (used[t] == 0) break;
  96.         int pp = t,ff = INF;
  97.         while(p[pp])
  98.         {
  99.             ff = min(ff,p[pp] -> c - p[pp] -> f);
  100.             pp = p[pp] -> from;
  101.         }
  102.         pp = t;
  103.         while(p[pp])
  104.         {
  105.             p[pp] -> f += ff;
  106.             p[pp] -> rev -> f -= ff;
  107.             pp = p[pp] -> from;
  108.         }
  109.     }
  110.     for(int i = 0; i < n; i++)
  111.     {
  112.         for(size_t j = 0; j < g[i].size(); j++)
  113.             if (g[i][j].to < n + m)
  114.                 cout<<a[i]<<"/"<<b[g[i][j].to - n]<<": "<<g[i][j].f<<endl;
  115.         if (i == n - 1) cout<<"ok"<<endl;
  116.     }
  117.     cout<<"here"<<endl;
  118.     return 0;
  119. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement