[Solution][Network Flow]SDOI2009 最优图像

【题目】

戳这里

【思路】

网络流。建模比较显然。

建立超级源、超级汇,将每一行和每一列分别建立点,从每一行到每一列连一条容量为1,费用为机率对数的边(如机率为0则不连),从超级源到每一行连一条容量为当前行1的个数,费用为0的边,从每一列到超级汇连一条容量为当前列1的个数,费用为0的边。跑一边最大费用最大流,然后枚举行列之间的边,如果满流,证明这个位置是1.

可以连负费用的边转化为最小费用最大流。

重要的一点是普通的spfa费用流会超时40%。。。

所以学习了一下ZKW大牛的费用流,对于稠密图(比如二分图)非常快。。。

【代码】

#include<cstdio>
#include<cmath>
#include<cstring>
#define Min(a , b) (a)<(b)?(a):(b)
const int INF = 0x3f3f3f3f;
int head[203] , cur[203] , next[20500] , end[20500] , flow[20500] , ind = 2;
long double cost[20500] , dis[203];
bool vis[203];
void addedge(int a , int b , int _flow , double _cost)
{
    int q = ind++;
    end[q] = b;
    next[q] = head[a];
    head[a] = q;
    flow[q] = _flow;
    cost[q] = _cost;
}
int S , T;
double Tot_cost;
int getflow(int p , int maxflow)
{
    if (p == T)
    {
        Tot_cost += maxflow * dis[S];
        return maxflow;
    }
    vis[p] = 1;
    int j;
    for(j = head[p] ; j ; j = next[j])
    {
        if (flow[j] && !vis[end[j]] && dis[end[j]] + cost[j] == dis[p])
        {
            int toflow = getflow(end[j] , Min(flow[j] , maxflow));
            if (toflow)
            {
                flow[j] -=toflow;
                flow[j ^ 1] += toflow;
                cur[p] = j;
                return toflow;
            }
        }
    }
    return 0;
}
bool newlabel()
{
    int i , j;
    long double Mindist = 1e100;
    for(i = S ; i <= T ; ++i)
    {
        if (vis[i])
        {
            for(j = head[i] ; j ; j = next[j])
            {
                if (flow[j] && !vis[end[j]] && dis[end[j]] + cost[j] - dis[i] < Mindist)
                    Mindist = dis[end[j]] + cost[j] - dis[i];
                 
            }
        }
    }
    if (Mindist == 1e100)
        return 0;
    for(i = S ; i <= T ; ++i)
    {
        if (vis[i])
        {
            vis[i] = 0;
            dis[i] += Mindist;
            cur[i] = head[i];
        }
    }
    return 1;
}
void maxcost()
{
    for(register int i = S ; i <= T ; ++i)
        cur[i] = head[i];
    do
    {
        while(getflow(S , 10000))
            memset(vis , 0 , sizeof(vis));
    }
    while(newlabel());
}
bool ans[203][203];
int main()
{
    int n , m;
    scanf("%d%d" , &n , &m);
    S = 0 , T = n + m + 1;
    register int i , j;
    int x;
    for(i = 1 ; i <= n ; ++i)
    for(j = 1 ; j <= m ; ++j)
    {
        scanf("%d" ,&x);
        if (x)
        {
            addedge(i , n + j , 1 , -log(x/double(100)));
            addedge(n + j , i , 0 , log(x/double(100)));
        }
    }
    for(i = 1 ; i <= n ; ++i)
    {
        scanf("%d" , &x);
        addedge(S , i , x , 0);
        addedge(i , S , 0 , 0);
    }
    for(i = 1 ; i <= m ; ++i)
    {
        scanf("%d" , &x);
        addedge(n + i , T , x , 0);
        addedge(T , n + i , 0 , 0);
    }
    maxcost();
    for(i = 1 ; i <= n ; ++i)
    {
        for(j = head[i] ; j ;j = next[j])
        {
            if (!flow[j])
            {
                ans[i][end[j] - n] = 1;
            }
        }
    }
    for(i = 1 ; i <= n ; ++i)
    {
        for(j = 1 ; j <= m ; ++j)
            if (ans[i][j])
                putchar('1');
            else
                putchar('0');
        puts("");
    }
    return 0;
}
comments powered by Disqus