Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<iostream>
- #include<stdio.h>
- #include<string.h>
- #include<vector>
- #include<queue>
- #include<map>
- #define pb push_back
- #define ppb pop_back
- #define mp make_pair
- #define all(x) (x).begin(),(x).end()
- #define sqr(x) (x) * (x)
- using namespace std;
- typedef pair<int, int> pii;
- struct edge
- {
- int from;
- int to;
- int c;
- int f;
- edge *rev;
- edge() : from(-1), to(-1), c(0), f(0), rev(NULL) {}
- edge(int from, int to, int c, int f, edge *rev) : from(from), to(to), c(c), f(f), rev(rev) {}
- };
- const int INF = 1000000000;
- int used[22];
- vector<edge*> p(22);
- vector< vector<edge> > g(22);
- void addEdge(int from, int to, int cnt)
- {
- g[from].pb(edge(from,to,cnt,0,NULL));
- g[to].pb(edge(to,from,0,0,NULL));
- g[from].back().rev = &g[to].back();
- g[to].back().rev = &g[from].back();
- }
- int main()
- {
- freopen("raceclass.in","r",stdin);
- freopen("raceclass.out","w",stdout);
- map<string, int> mp;
- int n,m,k,s,t,cnt;
- cin>>n>>m;
- s = n + m;
- t = n + m + 1;
- vector<string> a(n),b(m);
- string str,str1,str2;
- for(int i = 0; i < n; i++)
- {
- cin>>cnt;
- getline(cin,str);
- str.erase(0,1);
- a[i] = str;
- mp[str] = i;
- addEdge(s,i,cnt);
- }
- for(int i = 0; i < m; i++)
- {
- cin>>cnt;
- getline(cin,str);
- str.erase(0,1);
- b[i] = str;
- mp[str] = i + n;
- addEdge(i + n,t,cnt);
- }
- cin>>k;
- getline(cin,str);
- for(int i = 0; i < k; i++)
- {
- getline(cin,str);
- size_t pos = str.find("/");
- str1 = str.substr(0,pos);
- str.erase(0,pos + 1);
- str2 = str;
- addEdge(mp[str1],mp[str2],INF);
- }
- cout<<1<<endl;
- queue<int> q;
- while(true)
- {
- memset(used,0,sizeof(used));
- used[s] = 1;
- p[s] = NULL;
- q.push(s);
- while(!q.empty())
- {
- int from = q.front();
- q.pop();
- for(size_t i = 0; i < g[from].size(); i++)
- if (!used[g[from][i].to] && g[from][i].c - g[from][i].f > 0)
- {
- p[g[from][i].to] = &g[from][i];
- used[g[from][i].to] = 1;
- q.push(g[from][i].to);
- }
- }
- if (used[t] == 0) break;
- int pp = t,ff = INF;
- while(p[pp])
- {
- ff = min(ff,p[pp] -> c - p[pp] -> f);
- pp = p[pp] -> from;
- }
- pp = t;
- while(p[pp])
- {
- p[pp] -> f += ff;
- p[pp] -> rev -> f -= ff;
- pp = p[pp] -> from;
- }
- }
- for(int i = 0; i < n; i++)
- {
- for(size_t j = 0; j < g[i].size(); j++)
- if (g[i][j].to < n + m)
- cout<<a[i]<<"/"<<b[g[i][j].to - n]<<": "<<g[i][j].f<<endl;
- if (i == n - 1) cout<<"ok"<<endl;
- }
- cout<<"here"<<endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement