【2014 Multi-University Training Contest 3 1002】/【HDU 4888】 Redraw Beautiful Drawings

2020-12-13 05:40

阅读：561

标签：hdu 刷题最大流

不容易啊，终于可以补第二个题了！！

顺便说一句：模版写残了就不要怪出题人啊 ~ （这残废模版研究了好长时间才找出错）

题目大意：

有一个n*m的矩阵，每一个格子里都将有一个数。给你每一行数字之和和每一列数字之和。求每一个位置能填0~k之间的哪个数。如果有多种可能输出“Not Unique”，如果没有解输出“Impossible”，如果一组解则将其输出。

解题思路：

最大流：不可能的条件：是行之和和列之和不想等或者建图后的最大流与他们不想等。

多组的条件是：在最大流后的残流网络中有长度大于2的环（实际中最少大于3）。

下面是代码：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 

#define eps 1e-9
#define pi acos(-1.0)
#define inf 107374182  
#define inf64 1152921504606846976  
#define clear1(A, X, SIZE) memset(A, X, sizeof(A[0]) * (SIZE))
#define clearall(A, X) memset(A, X, sizeof(A))
#define memcopy1(A , X, SIZE) memcpy(A , X ,sizeof(X[0])*(SIZE))
#define memcopy1all(A, X) memcpy(A , X ,sizeof(X))
#define max( x, y )  ( ((x) > (y)) ? (x) : (y) )
#define min( x, y )  ( ((x) q;
    q.push(S);//源点
    deep[S]=0;
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        int p=head[u];
        while(p!=-1)
        {
            int v=edge[p].v;
            if(deep[v]==-1&&edge[p].w>0)
            {
                q.push(v);
                deep[v]=deep[u]+1;
            }
            p=edge[p].next;
        }
    }
    return deep[T]!=-1; //汇点

}
int DFS(int src ,int flow)
{
    if(src==T||flow==0)return flow;
    int sum=0,temp;
    int p=head[src];
    while(p!=-1)
    {
        int v=edge[p].v;
        if(deep[v]==deep[src]+1&&edge[p].w>0)
        {
            temp=DFS(v,min(flow-sum,edge[p].w));
            edge[p].w-=temp;
            edge[p^1].w+=temp;
            sum+=temp;
            if(flow-sum==0) return sum;
        }
        p=edge[p].next;
    }
    deep[src]=-1;
    return sum;
}
bool dfs(int u,int fa)
{
    for(int k=head[u]; k!=-1; k=edge[k].next)
    {
        if(k==(fa^1)) continue;
        if(edge[k].w)
        {
            if(vis[edge[k].v]) return true;
            vis[edge[k].v]=true;
            if(dfs(edge[k].v,k)) return true;
            vis[edge[k].v]=false;
        }
    }
    return false;
}
int mat[404][404];
void ptmat()
{
    printf("Unique\n");
    memset(mat,0,sizeof(mat));
    for(int u=1; un&&v1) printf(" ");
            printf("%d",mat[i][j]);
        }
        printf("\n");
    }
}
int main()
{
    while(scanf("%d%d%d",&n,&m,&K)!=EOF)
    {
        memset(head,-1,sizeof(head));
        nEdge=-1;
        S=0,T=n+m+1;
        int sum1=0,sum2=0,w;
        for(int i=1; i

【2014 Multi-University Training Contest 3 1002】/【HDU 4888】  Redraw Beautiful Drawings,搜素材,soscw.com
【2014 Multi-University Training Contest 3 1002】/【HDU 4888】  Redraw Beautiful Drawings
标签：hdu   刷题   最大流   
原文地址：http://blog.csdn.net/lin375691011/article/details/38305797

上一篇：CSS的语法和设置方式

下一篇：python中通过元类(TYPE)简单实现对象关系映射(ORM)

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：【2014 Multi-University Training Contest 3 1002】/【HDU 4888】 Redraw Beautiful Drawings
文章链接：http://soscw.com/essay/31530.html

亲，登录后才可以留言！

【2014 Multi-University Training Contest 3 1002】/【HDU 4888】 Redraw Beautiful Drawings

评论

热门文章

推荐文章

最新文章

置顶文章