HDU 4888 Redraw Beautiful Drawings 网络流 建图

标签：blog   os   io   for   2014   amp   size   ios   

题意：

给定n, m, k

下面n个整数 a[n]

下面m个整数 b[n]

用数字[0,k]构造一个n*m的矩阵

若有唯一解则输出这个矩阵，若有多解输出Not Unique，若无解输出Impossible

思路：网络流，，，

n行当成n个点，m列当成m个点

从行-列连一条流量为k的边，然后源点-行连一条a[i]的边， 列-汇点 流量为b[i]

瞎了，该退役了 T^T

#include
#include
#include
#include
#include
#include
#include
using namespace std;

#define ll int

#define N 1005
#define M 200000
#define inf 107374182
#define inf64 1152921504606846976
struct Edge{
    ll from, to, cap, nex;
}edge[M*2];//注意这个一定要够大 不然会re 还有反向弧

ll head[N], edgenum;
void add(ll u, ll v, ll cap, ll rw = 0){ //如果是有向边则：add(u,v,cap); 如果是无向边则：add(u,v,cap,cap);
    Edge E = { u, v, cap, head[u]};
    edge[ edgenum ] = E;
    head[u] = edgenum ++;

    Edge E2= { v, u, rw,  head[v]};
    edge[ edgenum ] = E2;
    head[v] = edgenum ++;
}
ll sign[N];
bool BFS(ll from, ll to){
    memset(sign, -1, sizeof(sign));
    sign[from] = 0;

    queueq;
    q.push(from);
    while( !q.empty() ){
        ll u = q.front(); q.pop();
        for(ll i = head[u]; i!=-1; i = edge[i].nex)
        {
            ll v = edge[i].to;
            if(sign[v]==-1 && edge[i].cap)
            {
                sign[v] = sign[u] + 1, q.push(v);
                if(sign[to] != -1)return true;
            }
        }
    }
    return false;
}
ll Stack[N], top, cur[N];
ll Dinic(ll from, ll to){
    ll ans = 0;
    while( BFS(from, to) )
    {
        memcpy(cur, head, sizeof(head));
        ll u = from;      top = 0;
        while(1)
        {
            if(u == to)
            {
                ll flow = inf, loc;//loc 表示 Stack 中 cap 最小的边
                for(ll i = 0; i  edge[ Stack[i] ].cap)
                    {
                        flow = edge[Stack[i]].cap;
                        loc = i;
                    }

                    for(ll i = 0; i 


HDU 4888 Redraw Beautiful Drawings 网络流 建图,搜素材,soscw.com
HDU 4888 Redraw Beautiful Drawings 网络流 建图
标签：blog   os   io   for   2014   amp   size   ios   
原文地址：http://blog.csdn.net/qq574857122/article/details/38276447