zoj 2567 Trade

#include<cstdio>#include<cstring>#include<cstdlib>#include<cmath>#include<algorithm>#include<string>#include<map>#include<set>#include<iostream>#include<vector>#include<queue>using namespace std;#define sz(v) ((int)(v).size())#define rep(i, n) for (int i = 0; i < (n); ++i)#define repf(i, a, b) for (int i = (a); i <= (b); ++i)#define repd(i, a, b) for (int i = (a); i >= (b); --i)#define clr(x) memset(x,0,sizeof(x))#define clrs( x , y ) memset(x,y,sizeof(x))#define out(x) printf(#x" %dn", x)#define sqr(x) ((x) * (x))typedef long long lint;const int maxint = -1u>>3;const double eps = 1e-8;int sgn(const double &x) { return (x > eps) - (x < -eps); }const int maxn = 1000 + 10;struct Graph { struct Adj { int v, c, b, id; Adj(int _v, int _c, int _id, int _b) : v(_v), c(_c), id(_id), b(_b) {} Adj(){} }; vector<int> e[maxn]; int n, SS, TT, h[maxn], cnt[maxn], S, T; int du[maxn]; vector<Adj> adj[maxn]; void clear() { memset(du, 0, sizeof(du)); for (int i = 0; i < n; i++) { adj[i].clear(); } n = 0; } void insert(int u, int v, int c, int id = 0, int d = 0) { n = max(n, max(u, v) + 1); adj[u].push_back(Adj(v, c, id, adj[v].size())); adj[v].push_back(Adj(u, c * d, id, adj[u].size() - 1)); } int maxflow(int _S, int _T) { S = _S, T = _T; fill(h, h + n, 0); fill(cnt, cnt + n, 0); int flow = 0; while (h[S] < n) { flow += dfs(S, maxint); } return flow; } int dfs(int u, int flow) { if (u == T) { return flow; } int minh = n - 1, ct = 0; for (vector<Adj>::iterator it = adj[u].begin(); flow && it != adj[u].end(); ++it) { if (it->c) { if (h[it->v] + 1 == h[u]) { int k = dfs(it->v, min(it->c, flow)); if (k) { it->c -= k; adj[it->v][it->b].c += k; flow -= k; ct += k; } if (h[S] >= n) { return ct; } } minh = min(minh, h[it->v]); } } if (ct) { return ct; } if (--cnt[h[u]] == 0) { h[S] = n; } h[u] = minh + 1; ++cnt[h[u]]; return 0; } void _insert(int u, int v, int low, int up, int id = 0, int d = 0) { du[u] -= low; du[v] += low; insert(u, v, up - low, id, d); } void build() { SS = n; TT = n + 1; n = TT + 1;  rep (i, n) { if (du[i] < 0)  insert(i, TT, abs(du[i])); else if (du[i] > 0) { insert(SS, i, abs(du[i])); } } } bool check() { rep (i, sz(adj[SS])) { if (adj[SS][i].c != 0) return false; } return true; }  int minflow(int s, int t) { build(); int h1 = maxflow(SS, TT); insert(t, s, maxint);  int h2 = maxflow(SS, TT); if (!check()) return -1; int res = 0; rep (i, sz(adj[s])) { if (adj[s][i].v == t) { res += adj[s][adj[t][i].b].c;  } } return res; }}G;vector<int> e[maxn];int du[maxn];int SS, TT, S, T;int n, m, tt;void init() { S = n + m; T = S + 1; G.clear(); rep (i, tt) { int x, y; scanf("%d%d", &x, &y); x--, y--; G._insert(x, n + y, 0, 1, i + 1); }  rep (i, n) { G._insert(S, i, 2, n + m); } rep (i, m) { G._insert(i + n, T, 2, n + m); }}void gao() { int res = G.minflow(S, T); if (res == -1) { printf("-1n"); return; } vector<int> ans; ans.clear(); rep (i, n) { rep (k, sz(G.adj[i])) { if (G.adj[i][k].c != 0) continue; int j = G.adj[i][k].v; if (n <= j && j < m + n) { ans.push_back(G.adj[i][k].id); } } } printf("%dn", sz(ans)); rep (i, sz(ans)) { if (i != 0) printf(" "); printf("%d", ans[i]); } if (sz(ans) != 0) puts("");}int main() { while (scanf("%d%d%d", &n, &m, &tt) == 3) { init(); gao();  } return 0;}