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

Re:有人能办忙看看吗?WA一晚上了都,谢谢!

Posted by cangqiongzhiding at 2018-09-30 09:27:40 on Problem 3281
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator