| ||||||||||
| 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