Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:有人能办忙看看吗?WA一晚上了都,谢谢!In Reply To:有人能办忙看看吗?WA一晚上了都,谢谢! Posted by:histar64 at 2016-02-29 21:47:08 > #include <cstdio> > #include <queue> > > using namespace std; > > #define REP(i, s, t) for (int i = (s); i <= (t); i++) > > const int INF = (int)2e9; > const int N = (int)4e2 + 50; > const int M = (int)6e5 + 50; > > int head[N], cnt = 1; > struct edge {int to, next, v;} e[M << 1]; > inline void ins(int x, int y, int v) > { > e[++cnt] = (edge){y, head[x], v}; head[x] = cnt; > e[++cnt] = (edge){x, head[y], 0}; head[y] = cnt; > } > > queue<int> q; > int n, f, d, lev[N], cur[N]; > > bool bfs() > { > REP(i, 1, n) > lev[i] = -1; > lev[1] = 0; > q.push(1); > while (!q.empty()) { > int x = q.front(); q.pop(); > for (int i = head[x]; i; i = e[i].next) { > if (e[i].v && lev[e[i].to] == -1) { > lev[e[i].to] = lev[x] + 1; > q.push(e[i].to); > } > } > } > return lev[n] != -1; > } > > int dfs(int x, int f) > { > if (x == n) > return f; > int usd = 0; > for (int i = cur[x]; i; i = e[i].next) { > if (e[i].v && lev[e[i].to] == lev[x] + 1) { > int tmp = dfs(e[i].to, min(e[i].v, f - usd)); > e[i].v -= tmp; > if (e[i].v) > cur[x] = i; > e[i^1].v += tmp; > usd += tmp; > if (usd == f) > return f; > } > } > if (!usd) > lev[x] = -1; > return usd; > } > > int dinic() > { > int mxflw = 0; > while (bfs()) { > REP(i, 1, n) > cur[i] = head[i]; > mxflw += dfs(1, INF); > } > return mxflw; > } > > // 1, 2 ~ n+1, n+2 ~ n*2+1, n*2+2 ~ n*2+f+1, n*2+f+2 ~ n*2+f+d+1, n*2+f+d+2; > > #define COW1 1 > #define COW2 2 > #define FOOD 3 > #define DRK 4 > #define S 1 > #define T n*2+f+d+2 > > inline int gtp(int type, int cod) > { > if (type == COW1) > return cod + 1; > else if (type == COW2) > return cod + n + 1; > else if (type == FOOD) > return cod + n*2 + 1; > else > return cod + n*2 + f + 1; > } > > void input() > { > scanf("%d%d%d", &n, &f, &d); > REP(i, 1, f) > ins(gtp(COW1, i), gtp(COW2, i), 1); > REP(i, 1, f) > ins(S, gtp(FOOD, i), 1); > REP(i, 1, d) > ins(gtp(DRK, i), T, 1); > REP(i, 1, n) { > int fi, di, x; > scanf("%d%d", &fi, &di); > REP(j, 1, fi) { > scanf("%d", &x); > ins(gtp(FOOD, x), gtp(COW1, i), 1); > } > REP(j, 1, di) { > scanf("%d", &x); > ins(gtp(COW2, i), gtp(DRK, x), 1); > } > } > n = T; > } > > void go() > { > int ans = dinic(); > printf("%d\n", ans); > } > > int main() > { > freopen("file.in", "r", stdin); > // freopen("file.out", "w", stdout); > input(); go(); > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator