《网络流学习笔记04 && NYOJ 489 哭泣天使（建边，超级源点和汇点）》

链接：click here

题意描述：

哭泣天使

描述

Doctor Who乘着Tardis带着Amy来到了一个星球，一开Tadis大门，发现这个星球上有个壮观的石像群，全是一些天使石像，有的石像在哭泣，有的石像像在微笑，共有m行n列，Doctor用“音速起子”扫描了一下整个石像群，得到了每行天使中在哭泣的天使的个数。当他与Amy在这里行走了一段时间之后，Doctor忽然想起了什么，怀疑这些石像是不是传说中的一种黑暗生物——“哭泣天使”——一种看似石像，却会在人不看它的时候移动，会强制把人送回某个过去的时间点，并借此汲取时间能量的生物。Doctor可不想自己和Amy迷失在一个未知的时间点里，于是Doctor立刻用“音速起子”又扫描了整个石像群，想再看看每行的在哭泣的天使个数与刚才是否相符，但是，越急就越容易出错，他一不小心扫描错了，扫描出了每列中哭泣的天使的个数。现在，由于音速起子的能量不足了，他不能够再次扫描，他想根据已有的数据判断出是否有天使改变了自己的表情，从哭泣变成不哭泣或者从不哭泣变成哭泣了。

输入

第一行是一个整数T，表示共有T组测试数据(T<=50)
每组测试数据第一行是两个整数m,n(0<m,n<=300)分别表示行数和列数
随后的两行分别有m个数和n个数分别表示对应m行中哭泣的天使石像的个数与对应n个列中哭泣的天使石像的个数。

输出

如果能根据已有信息判断出必然有石像改变了表情，则输出Terrible
如果根据已有信息无法确定石像发生了改变，则输出Not Sure (有时，你确定两次扫描时状态相同，但由于不确定之间是否发生过改变，故也输出Not Sure)

样例输入

2
2 3
1 1
1 1 0
3 3
0 1 2
3 0 0

样例输出

Not Sure
Terrible

思路：该题主要在于 1建边。
                                    2 建超级源点和超级汇点。
因为一行和一列单独确定一个点，所以把所有的行和列当成点建边，容量为1，再建一个源点s，与所有的行相连，容量为每一行哭泣天使的数量，建立一个汇点t，与所有的列相连，容量为相应列哭泣天使的容量，然后求最大流，与之前得到行的数量比较之。另外，如果输入的数据行和列的和都不一样，那么不需要判断，必然有天使改变状态，直接输出Terrible，否则输出Not Sure。

代码（Dinic实现）：

#include <math.h>
#include <queue>
#include <deque>
#include <vector>
#include <stack>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
int dir[4][2]= {{1,0},{-1,0},{0,1},{0,-1}};
const double eps = 1e-6;
const double Pi = acos(-1.0);
static const int INF = ~0U >> 2;//比0x3f3f3f3f还大
static const int MAXN = 600 + 5;
struct Edge
{
    int from,to,cap,flow;
    Edge(int f,int t,int c,int ff)
        :from(f),to(t),cap(c),flow(ff) {};
};
vector<Edge> edges;
vector<int> G[MAXN];
int N,M,S,T,i,j;
int iter[MAXN],level[MAXN];
bool vis[MAXN];
void Init()
{
    S = 0;
    T = N+M+1;
    for(int i = 0; i <= T; ++i)
        G[i].clear();
    edges.clear();
}
bool add_edge(int from,int to,int cap)
{
    edges.push_back(Edge(from,to,cap,0));
    edges.push_back(Edge(to,from,0,0));
    int sz = edges.size();
    G[from].push_back(sz-2);
    G[to].push_back(sz-1);
}
bool BFS()
{
    memset(vis,false,sizeof(vis));
    level[S] = 0;
    vis[S] = true;
    queue<int> Q;
    Q.push(S);
    while(!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        for(int i = 0; i < (int)G[u].size(); ++i)
        {
            Edge& e = edges[G[u][i]];
            if(!vis[e.to]&&e.cap > e.flow)
            {
                vis[e.to] = true;
                level[e.to] = level[u] + 1;
                Q.push(e.to);
            }
        }
    }
    return vis[T];
}
int DFS(int u,int a)
{
    if(u==T||a==0)
        return a;
    int f,flow = 0;
    for(int& i = iter[u]; i < (int)G[u].size(); ++i)
    {
        Edge& e = edges[G[u][i]];
        if(level[e.to]==level[u]+1&&(f=DFS(e.to,min(a,e.cap-e.flow)))>0)
        {
            e.flow += f;
            edges[G[u][i]^1].flow -= f;
            flow += f;
            a -= f;
            if(a==0)break;
        }
    }
    return flow;
}
int Dinic()
{
    int flow = 0;
    while(BFS())
    {
        memset(iter,0,sizeof(iter));
        flow += DFS(S,INF);
    }
    return flow;
}
bool Solve()                                     //关键
{
    int c,sum1= 0,sum2 = 0;
    scanf("%d%d",&N,&M);
    Init();
    for(int i = 1; i <= N; ++i)
    {
        scanf("%d",&c);
        sum1+= c;
        add_edge(S,i,c);
    }
    for(int i = 1; i <= M; ++i)
    {
        scanf("%d",&c);
        sum2+= c;
        add_edge(i+N,T,c);
    }
    if(sum1!= sum2)
        return true;
    for(int i = 1; i <= N; ++i)
        for(int j = 1; j <= M; ++j)
            add_edge(i,j+N,1);
    int flow = Dinic();
    if(flow == sum1)
        return false;
    return true;
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        if(Solve())
            puts("Terrible");
        else
            puts("Not Sure");
    }
    return 0;
    //printf("%d %d\n",0x3f3f3f3f,~0U >> 2);
}

《网络流学习笔记04 && NYOJ 489 哭泣天使（建边，超级源点和汇点）》

原文：http://blog.csdn.net/u013050857/article/details/43745411