hdu 4888 Redraw Beautiful Drawings(最大流，判环)

2020-12-13 05:41

阅读：277

标签：最大流

http://acm.hdu.edu.cn/showproblem.php?pid=4888

添加一个源点与汇点，建图如下：

1. 源点 -> 每一行对应的点，流量限制为该行的和

2. 每一行对应的点 -> 每一列对应的点，流量限制为 K

3. 每一列对应的点 -> 汇点，流量限制为该列的和

求一遍最大流，若最大流与矩阵之和相等，说明有解，否则无解。判断唯一解，是判断残量网络中是否存在一个长度大于2的环，若存在说明有多解，否则有唯一解，解就是每条边行i->列j的流量。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define LL long long
#define _LL __int64
#define eps 1e-12
#define PI acos(-1.0)
#define C 240
#define S 20
using namespace std;

const int INF = 0x3f3f3f3f;

const int maxn = 810;
const int maxm = 160000+810;

struct node
{
    int u,v,w,next;
} edge[maxm que;
    while(!que.empty()) que.pop();
    memset(dis,-1,sizeof(dis));
    dis[s] = 0;
    que.push(s);

    while(!que.empty())
    {
        int u = que.front();
        que.pop();

        for(int i = head[u]; i != -1; i = edge[i].next)
        {
            int v = edge[i].v;
            if(dis[v] == -1 && edge[i].w)
            {
                dis[v] = dis[u]+1;
                que.push(v);
            }
        }
    }
    if(dis[t] == -1)
        return false;
    return true;
}

int dfs(int u, int delta)
{
    if(u == t || delta == 0) return delta;
    int dd;
    int ret = 0;
    for(int i = head[u]; i != -1 && delta; i = edge[i].next)
    {
        if(dis[edge[i].v] == dis[u]+1 && (dd = dfs(edge[i].v,min(delta,edge[i].w))))
        {
            edge[i].w -= dd;
            edge[i^1].w += dd;
            delta -= dd;
            ret += dd;
            if(delta == 0)
                return ret;
        }
    }
	dis[u] = -1;
	return ret;
}

int Dinic()
{
    int ret = 0;
    while(bfs())
    {
        ret += dfs(s,INF);
    }
    return ret;
}

int dfs_1(int u,int fa)
{
    for(int i=head[u]; i!=-1; i=edge[i].next)
    {
        if(i==(fa^1)) continue;
        if(edge[i].w)
        {
            if(vis[edge[i].v]) return 1;
            vis[edge[i].v]=1;
            if(dfs_1(edge[i].v,i)) return 1;
            vis[edge[i].v]=0;
        }
    }
    return 0;
}

void putmat()
{
	int f[410][410];
	printf("Unique\n");
	for(int u = 1; u  n && v 







hdu 4888 Redraw Beautiful Drawings(最大流，判环),搜素材,soscw.com
hdu 4888 Redraw Beautiful Drawings(最大流，判环)
标签：最大流
原文地址：http://blog.csdn.net/u013081425/article/details/38311349

上一篇：nutch2.1抓取中文网站

下一篇：Python3基础 print %xX 十六进制大小写

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：hdu 4888 Redraw Beautiful Drawings(最大流，判环)
文章链接：http://soscw.com/essay/31582.html

亲，登录后才可以留言！

hdu 4888 Redraw Beautiful Drawings(最大流，判环)

评论

热门文章

推荐文章

最新文章

置顶文章