HDUOJ--4888--Redraw Beautiful Drawings【isap】网络流+判环

发布时间:2017-7-9 7:24:35编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDUOJ--4888--Redraw Beautiful Drawings【isap】网络流+判环 ",主要涉及到HDUOJ--4888--Redraw Beautiful Drawings【isap】网络流+判环 方面的内容,对于HDUOJ--4888--Redraw Beautiful Drawings【isap】网络流+判环 感兴趣的同学可以参考一下。

链接:http://acm.hdu.edu.cn/showproblem.php?

pid=4888

题意:一个矩阵。限定每行行和、列和,每一个格子数字不超过k,问矩阵是否存在,如存在推断有单解还是多解。


思路:之前多校的题目,那时候还不会网络流,如今A掉了,矩阵的建图模型,推断网络流是否可行仅仅要推断最大流是否等于总行和或总列和就可以,判环是看的别人的解题报告,方法是使用dfs查找残余网络中是否有还存在容量的弧形成了环,假设有,说明能够通过这个环改变容量网络内部的增广路方式。而源汇的流量是不会变的。就说明存在多解。假设没有环,就是单一解。

建图:源点向每一个行节点连弧,容量为该行行和,每一个列节点向汇点连边,容量为每一个列和,每一个行节点与每一个列节点之间连边,容量为k。

细节:之前WA了,我以为是minm赋值的问题,实际上minm赋值为nn-1是没问题的,仅仅要赋值大于等于nn-1即可了。WA的地方在dist[i]=-1时须要特判。统计层次时对-1不会统计,假设不加推断,会使数组下标变成-1,就错了。HDU上不是RE。是WA。之前一直没加过也AC了两题,如今知道了。



#include<cstring>#include<string>#include<fstream>#include<iostream>#include<iomanip>#include<cstdio>#include<cctype>#include<algorithm>#include<queue>#include<map>#include<set>#include<vector>#include<stack>#include<ctime>#include<cstdlib>#include<functional>#include<cmath>using namespace std;#define PI acos(-1.0)#define MAXN 50100#define eps 1e-7#define INF 0x7FFFFFFF#define LLINF 0x7FFFFFFFFFFFFFFF#define seed 131#define MOD 1000000007#define ll long long#define ull unsigned ll#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1struct node{    int u,v,w,next;}edge[500000];int head[820],dist[820],cur[820],fa[820],num[820],vis[820];int n,m,k,cnt,nn,src,sink;void add_edge(int a,int b,int c){    edge[cnt].u = a;    edge[cnt].v = b;    edge[cnt].w = c;    edge[cnt].next = head[a];    head[a] = cnt++;}void bfs(){    int x,i,j;    queue<int> q;    memset(dist,-1,sizeof(dist));    q.push(sink);    dist[sink] = 0;    while(!q.empty()){        x = q.front();        q.pop();        for(i=head[x];i!=-1;i=edge[i].next){            if(dist[edge[i].v]<0){                dist[edge[i].v] = dist[x] + 1;                q.push(edge[i].v);            }



上一篇:AngualrJS之服务器端通信
下一篇:git pull refusing to merge unrelated histories

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款