hdu 4888 Redraw Beautiful Drawings 最大流

2020-12-13 05:40

阅读：266

标签：os io for ar line amp size ios

好难好难，将行列当成X和Y，源汇点连接各自的X，Y集，容量为行列的和，相当于从源点流向每一行，然后分配流量给每一列，最后流入汇点，这样执意要判断最后是否满流，就知道有没有解，而解就是每一行流向每一列多少流量。

关键在于怎么判断多解的情况。我想不到啊T_T

题解说，找到一个长度大于2的环。

想了一想，也就是找到还有剩余流量的环，如果找到了，我就可以把其中一条边的流量转移，因为是一个环，所以它又会达到平衡，不会破坏最大流，但是这样转移后，解就多了一种，所以只要判断是否有一个长度大于2的环就够了。

这里长度为什么要大于2，因为建图时的反向弧会导致 A->B并且B立刻->A，这样的话，也是一个环，但转移这条环的流量却会破坏最大流。

所以我们在用dfs找环的时候，要注意不能立刻走反向弧。

dinic用了当前弧优化。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#define eps  1e-12
#define INF   0x7fffffff
#define maxn 1005
using namespace std;
int n,m,k;
int en;
int st,ed;
int dis[maxn],cur[maxn];
int que[999999];
struct edge
{
    int to,c,next;
};
edge e[999999];
int head[maxn];
void add(int a,int b,int c)
{
    e[en].to=b;
    e[en].c=c;
    e[en].next=head[a];
    head[a]=en++;
    e[en].to=a;
    e[en].c=0;
    e[en].next=head[b];
    head[b]=en++;
}
int bfs()
{
    memset(dis,-1,sizeof(dis));
    dis[st]=0;
    int front=0,rear=0;
    que[rear++]=st;
    while(front '9')
    {
        ch = getchar();
    }
    do
    {
        data = data*10 + ch-'0';
        ch = getchar();
    }while (ch >= '0' && ch =1&&e[j].ton&&e[j].to

hdu 4888 Redraw Beautiful Drawings 最大流,搜素材,soscw.com
hdu 4888 Redraw Beautiful Drawings 最大流
标签：os   io   for   ar   line   amp   size   ios   
原文地址：http://blog.csdn.net/t1019256391/article/details/38294985

上一篇：JQuery打造下拉框联动效果

下一篇：知道堆排序吗?

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

亲，登录后才可以留言！

hdu 4888 Redraw Beautiful Drawings 最大流

评论

热门文章

推荐文章

最新文章

置顶文章