首页 > 代码库 > 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。
细节:我用的我之前AC过题目的isap模板,但是WA了,我debug之后发现错误不会在建图和判环里,然后就和别人的isap代码对照,发现了一个不一样的地方,改之AC,不懂为何,不一样的地方代码中有注释。我的理解nn个点,源点src的层次是0,则最大的层次应该就是nn-1,但是minm初始化为nn-1是WA,初始化为nn就AC了。理论上应该是初始化大于等于nn-1都是可以的,以后还是就初始化为nn吧避免莫名其妙的WA。
#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|1 struct 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)); memset(num,0,sizeof(num)); q.push(sink); dist[sink] = 0; num[0] = 1; 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; num[dist[edge[i].v]]++; q.push(edge[i].v); } } } } int augment() { int x=sink,a=INF; while(x!=src){ a = min(a,edge[fa[x]].w); x = edge[fa[x]].u; } x=sink; while(x!=src){ edge[fa[x]].w -= a; edge[fa[x]^1].w += a; x = edge[fa[x]].u; } return a; } int isap() { int i,x,ok,minm,flow=0; bfs(); for(i=0;i<=nn+5;i++) cur[i] = head[i]; x=src; while(dist[src]<nn){ if(x==sink){ flow += augment(); x = src; } ok=0; for(i=cur[x];i!=-1;i=edge[i].next){ if(edge[i].w && dist[x]==dist[edge[i].v]+1){ ok=1; fa[edge[i].v] = i; cur[x] = i; x = edge[i].v; break; } } if(!ok){ minm = nn; //minm = nn - 1 就WA for(i=head[x];i!=-1;i=edge[i].next) if(edge[i].w && dist[edge[i].v]<minm) minm=dist[edge[i].v]; if(--num[dist[x]]==0)break; num[dist[x]=minm+1]++; cur[x]=head[x]; if(x!=src) x=edge[fa[x]].u; } } return flow; } bool dfs(int u,int pre){ int i,j; if(vis[u]) return true; vis[u] = 1; for(i=head[u];i!=-1;i=edge[i].next){ if(edge[i].w>0&&edge[i].v!=pre&&dfs(edge[i].v,u)) return true; } vis[u] = 0; return false; } int row[410],col[410]; int ans[420][420]; int main(){ int i,j; int sumr,sumc; while(scanf("%d%d%d",&n,&m,&k)!=EOF){ memset(head,-1,sizeof(head)); sumr = sumc = 0; cnt = 0; src = http://www.mamicode.com/0;>HDUOJ--4888--Redraw Beautiful Drawings【isap】网络流+判环
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。