Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 有人能办忙看看吗？WA一晚上了都，谢谢！

Posted by histar64 at 2016-02-29 21:47:08 on Problem 3281
#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;

struct edge {int to, next, v;} e[M << 1];
inline void ins(int x, int y, int v)
{
}

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