POJ 1698 Alice's Chance 二分图多重匹配 网络最大流

题目链接：http://poj.org/problem?id=1698

题意：

爱丽丝要拍电影，有n部电影，规定爱丽丝每部电影在每个礼拜只有固定的几天可以拍电影，只可以拍前面w个礼拜，并

且这部电影要拍d天,问爱丽丝能不能拍完所有的电影

第一行代表有多少组数据

对于每组数据第一行代表有n部电影

接下来2到n+1行，每行代表一个电影，每行9个数，前面7个数，1代表拍，0代表不拍，第8个数代表要拍几天，第9个

数代表有几个礼拜时间拍

解法：

将电影作为X方点，每一天作为Y方点（最多50周，每周7天，所以共设350个Y方点），若第i个电影可以在第j天搞就连

边(i, j)。每个X方点的L值为该电影总共要搞多少天，每个Y方点的L值为1（每天最多只能搞一个电影），然后求二分图多

重最大匹配，若能使所有从源点连向X方点的边都满流，则输出Yes，否则输出No。

//POJ 1698

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
const int maxn = 410;
const int maxm = 40010;
const int INF = 0x3fffffff;
struct G
{
int v, cap, next;
    G() {}
    G(int v, int cap, int next) : v(v), cap(cap), next(next) {}
} E[maxm];
int p[maxn], T;
int d[maxn], temp_p[maxn], qw[maxn]; //d顶点到源点的距离标号,temp_p当前狐优化，qw队列
void init()
{
    memset(p, -1, sizeof(p));
    T = 0;
}
void add(int u, int v, int cap)
{
    E[T] = G(v, cap, p[u]);
    p[u] = T++;
    E[T] = G(u, 0, p[v]);
    p[v] = T++;
}
bool bfs(int st, int en, int n)
{
int i, u, v, head, tail;
for(i = 0; i <= n; i++) d[i] = -1;
    head = tail = 0;
    d[st] = 0;
qw[tail] = st;
while(head <= tail)
    {
        u = qw[head++];
for(i = p[u]; i + 1; i = E[i].next)
        {
            v = E[i].v;
if(d[v] == -1 && E[i].cap > 0)
            {
                d[v] = d[u] + 1;
qw[++tail] = v;
            }
        }
    }
return (d[en] != -1);
}
int dfs(int u, int en, int f)
{
if(u == en || f == 0) return f;
int flow = 0, temp;
for(; temp_p[u] + 1; temp_p[u] = E[temp_p[u]].next)
    {
        G& e = E[temp_p[u]];
if(d[u] + 1 == d[e.v])
        {
            temp = dfs(e.v, en, min(f, e.cap));
if(temp > 0)
            {
                e.cap -= temp;
                E[temp_p[u] ^ 1].cap += temp;
                flow += temp;
                f -= temp;
if(f == 0)  break;
            }
        }
    }
return flow;
}
int dinic(int st, int en, int n)
{
int i, ans = 0;
while(bfs(st, en, n))
    {
for(i = 0; i <= n; i++) temp_p[i] = p[i];
        ans += dfs(st, en, INF);
    }
return ans;
}

int f[25][9];
int t, n, D, W, k, sum, flag;
int source, sink;

int main()
{
    scanf("%d", &t);
while(t--){
        memset(f, 0, sizeof(f));
        init();
        sum = 0;
        source = 0;
        flag = 0;
        scanf("%d", &n);
for(int i = 1; i <= n; i++){
for(int j = 1; j <= 7; j++){
                scanf("%d", &f[i][j]);
            }
            scanf("%d%d", &D, &W);
            add(source, i, D); //源点和电影连边，流量为部数
            sum += D;
if(flag < W) flag = W;
for(int k = 0; k < W; k++){
for(int j = 1; j <= 7; j++){
if(f[i][j]){
                        add(i, j+n+7*k, 1); //电影和各周中相应的天数连边流量为1
                    }
                }
            }
        }
        sink = n + 7*flag + 1;
for(int i = 0; i < flag; i++){
for(int j = 1; j <= 7; j++){
                add(7*i+n+j, sink, 1);//将每个星期的周一到周日都和汇点相连,流量为1
            }
        }
int ans = dinic(source, sink, sink+1);
if(sum == ans) printf("Yes\n");
else printf("No\n");
    }
return 0;
}