poj 2396 Budget 很犀利的网络流~

建图，听某神犇说网络流建图不能看别人的，要自己建才能提高的快，自己想也挺适合哥的风格的，尼玛想了哥将近半个小时！！不过最后想出了然后自己还证明了还是挺有成就感的~

建图方法：

s连接每一行，每一列连接t，边的容量是行和列的容量，然后每一行的点连接每一列，就又产生了m*n条相互交错的边，每条边的正向容量初始化为正无穷，逆向容量初始化为0；这个图挺有对称感的吧~~比那种01建图美多了是吧！最后是对于限制条件，如果是‘=’号，把这条边的正向容量和逆向容量都变成v；如果是‘<’号且v-1小于正向容量，就让正向容量等于v-1；如果是‘>’号同理，比较逆向容量和 -(v+1)的大小，改变它的逆向容量。

最后是初始流量，把每条交错边的流量都初始为(-c逆)，为什么是（-c逆）呢其实很简单，（c正）和（c逆）本质上就是来限制流量的上下限的（ - c逆 <= f <= c正），流量必须要先等于它的下限，然后再慢慢增加达到最大流，如果下限都不能满足那就不可能满足了，直接return false。我建图的地方有判断的。

然后求最大流，如果最后的最大流就是等于边或行容量总和，直接输出每条交错边的流量；否则输出impossible。

可以证明找到最大流等于边容量和和有一种合理的方案是一个充要条件。

证明：

首先最大流是在满足，每一条边的限制条件下求得的，然后最大流等于边容量和说明每一条连接start和end的边都饱和了，说明每一种方案的sum都符合条件，所以这种方案是合理的方案。

然后证明能满足条件的话最大流一定和行总和相等，这个方向简直是废话了，满足条件说明每条边的流量在限制范围之内，且行和列已经饱和，当然能找到一个f使最大流和行总和相等！！！

代码很长，建图写了200行。。。

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
using namespace std;

#define pb push_back

struct zz
{
    int from;
    int to;
    int c;
    int f;
    int id;    
}zx,tz;

const int maxn=233;
const int maxc=22;
const int inf=0x3f3f3f3f;
const int end=230;

char cc;
vector<zz>g[maxn];
queue<int>q;
int T,m,n,c,tx,ty,xx,totalx,totaly,total,have;
int f[maxn][maxc]; 
int cz[maxn][maxc];    
int cn[maxn][maxc];
int cen[maxn+maxc];
int cx[maxn];
int cy[maxc];
int sx[maxn];
int sy[maxc];


bool in(int x,int y)
{
    if(cc=='=')
    {
        if(xx<=cz[x][y]) 
        {
            cz[x][y]=xx;
        }   
        else
        {
            return false;
        }
        if(xx+cn[x][y]>=0)
        {
            cn[x][y]=-xx;
        }
        else
        {
            return false;
        }
    }   
    else if(cc=='<')
    {
        if(xx - 1 < cz[x][y])
        {
            cz[x][y] = xx - 1;
        }         
        if(cz[x][y]+cn[x][y] < 0)
        {
            return false;
        }
    } 
    else if(cc=='>')
    {
        if(xx + 1 + cn[x][y] > 0)
        {
            cn[x][y]=-xx-1;    
        }   
        if(cz[x][y]+cn[x][y] < 0)
        {
            return false;
        }
    }
    return true;    
}

bool give()
{
    if(tx==0 && ty==0)
    {
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)       
            {
                if(!in(i,j))
                {
                    return false;
                }
            }
        }       
    }
    else if(tx == 0)
    {
        for(int i=1;i<=m;i++)
        {
            if(!in(i,ty))
            {
                return false;
            }
        }
    }
    else if(ty == 0)
    {   
        for(int i=1;i<=n;i++)       
        {
            if(!in(tx,i))
            {
                return false;
            }
        }
    }
    else
    {
        if(!in(tx,ty)) 
        {
            return false;
        }   
    }
    return true;
}

bool get()
{
    cin>>c;
    bool re=true;
    for(int i=1;i<=c;i++)
    {
        cin>>tx>>ty>>cc>>xx;
        if(!give())
        {
            re=false;       
        }
    }   
    return re;
}

bool build()
{   
    for(int i=0;i<maxn;i++)
    {
        g[i].clear();
    }    
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            f[i][j] = -cn[i][j];  
        }
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            sx[i]+=f[i][j];
        }
        have+=sx[i];
        if(sx[i]>cx[i])
        {
            return false;
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            sy[i]+=f[j][i];
        }
        if(sy[i]>cy[i])
        {
            return false;
        }
    }
    for(int i=1;i<=m;i++)
    {
        zx.from=0;
        zx.to=i;
        zx.c=cx[i];
        zx.f=sx[i];
        zx.id=g[i].size();
        g[0].push_back(zx);
        swap(zx.from,zx.to);
        zx.id=g[0].size()-1;
        zx.c=0;
        zx.f=-sx[i];
        g[i].push_back(zx);
    }
    for(int i=1;i<=n;i++)
    {
        zx.from=200+i;
        zx.to=end;
        zx.c=cy[i];
        zx.f=sy[i];
        zx.id=g[end].size();    
        g[200+i].pb(zx);
        swap(zx.from,zx.to);
        zx.id=g[200+i].size()-1;
        zx.c=0;
        zx.f=-sy[i];
        g[end].pb(zx);        
    }
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
        {
            zx.from=i;
            zx.to=200+j;
            zx.f=f[i][j];
            zx.c=cz[i][j];
            zx.id=g[200+j].size();
            g[i].pb(zx);
            swap(zx.from,zx.to);
            zx.f=-f[i][j];
            zx.c=cn[i][j];
            zx.id=g[i].size()-1;
            g[200+j].pb(zx);
        }                      
    }
    return true;  
}

bool bfs()
{
    memset(cen,-1,sizeof(cen));
    while(!q.empty())
    {
        q.pop();
    }
    q.push(0);
    cen[0]=0;
    int now,to;
    while(!q.empty())
    {
        now=q.front();
        q.pop();
        for(int i=0;i<g[now].size();i++)
        {
            to=g[now][i].to;
            if(g[now][i].c > g[now][i].f && cen[to]==-1)
            {
                cen[to]=cen[now]+1;
                q.push(to);
            }
        }   
    }
    return cen[end]!=-1;   
}

int dfs(int flow=inf,int now=0)
{   
    if(now==end)
    {
        return flow;
    }    
    int temp,sum=0;
    int to;
    for(int i=0;i<g[now].size();i++)
    {
        to=g[now][i].to;
        if ( g[now][i].c > g[now][i].f && flow > sum && cen[to] == cen[now] + 1 )     
        {
            temp = dfs( min ( g[now][i].c - g[now][i].f , flow - sum ) , to );
            sum+=temp;
            g[now][i].f += temp;    
            g[to][g[now][i].id].f -= temp;
            if(now<end && now && to && to<end)
            {
                if(to > 200)  
                {
                    f[now][to-200]=g[now][i].f;  
                }
                else if(now > 200)
                {    
                    f[to][now-200]=g[to][g[now][i].id].f;
                }
            }
        }                      
    }
    if(!sum) cen[now]=-1;
    return sum;
}

bool dinic()
{
    int ans=0;
    while(bfs())
    {
        ans+=dfs();    
    }   
    if(ans + have == total)
    {
        return true;
    }
    else    
    {
        return false;
    }
}

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>m>>n;
        have=totalx=totaly=0;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cz[i][j] = inf;
            }
        }      
        memset(f,0,sizeof(f));
        memset(cn,0,sizeof(cn));
        memset(sx,0,sizeof(sx));
        memset(sy,0,sizeof(sy));
        for(int i=1;i<=m;i++)
        {
            cin>>cx[i];
            totalx+=cx[i];
        }    
        for(int i=1;i<=n;i++)
        {
            cin>>cy[i];
            totaly+=cy[i];
        }
        total=totalx;
        if(!get())
        {
            cout<<"IMPOSSIBLE"<<endl;
            if(T) cout<<endl;
            continue;
        } 
        if(!build())
        {
            cout<<"IMPOSSIBLE"<<endl;
            if(T) cout<<endl;
            continue; 
        }   
        if(dinic())                        
        {
            for(int i=1;i<=m;i++)
            {
                for(int j=1;j<n;j++)
                {
                    cout<<f[i][j]<<" ";
                }
                cout<<f[i][n]<<endl;
            }
            if(T) cout<<endl;
            continue;
        }            
        else
        {
            cout<<"IMPOSSIBLE"<<endl;
            if(T) cout<<endl;
            continue;
        } 
    }   
    return 0;
}