首页 > 代码库 > hdu 4975 最大流及其唯一性判定(有向图环判断算法升级)
hdu 4975 最大流及其唯一性判定(有向图环判断算法升级)
就当时最大流再次复习吧。。动手敲一下。。。经典解法不想说了。。这题主要是坑时间,10个提交7个tle。
环的判断,曾经用简单dfs方法,这次的就tle了!别人说要用很屌的dinic,我感觉自己dinic不可能超时,坚信是判断环慢了,于是学习了新断环的方法:删除点/边!从某点进去,若该点的所有边都遍历过还是无功而返,那么该店以后不用再进入了(这么简单的道感觉自己应该要想到啊!愚蠢啊!)开始时用只删除边,还是tle!nb!于是自己删点又删边,一下到156ms,前5了!
#include<cstdio> #include<iostream> #include<queue> #include<cstring> #include<string> using namespace std; const int maxv=1200; const int maxe=2*501*501+2000; const int inf=0x3f3f3f3f; int n,m;int allsumn=0,allsumm=0; int nume=0;int e[maxe][3];int head[maxv]; bool flag; void inline adde(int i,int j,int c) { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume; e[nume++][2]=c; e[nume][0]=i;e[nume][1]=head[j];head[j]=nume; e[nume++][2]=0; } int lev[maxv];int vis[maxv]; int ss=0;int tt=0; bool bfs() { memset(lev,0,sizeof(lev)); memset(vis,0,sizeof(vis)); queue<int>q; q.push(ss); vis[ss]=1; while(!q.empty()) { int cur=q.front(); q.pop(); for(int i=head[cur];i!=-1;i=e[i][1]) { int v=e[i][0]; if(e[i][2]>0&&!vis[v]) { lev[v]=lev[cur]+1; // if(v==tt)return 1; //这句不加,速度更快 q.push(v); vis[v]=1; } } } return vis[tt]; } int dfs(int u,int minf) { if(u==tt||minf==0)return minf; int sumf=0,f; for(int i=head[u];i!=-1&&minf;i=e[i][1]) { int v=e[i][0]; if(lev[v]==lev[u]+1&&e[i][2]>0) { f=dfs(v,e[i][2]<minf?e[i][2]:minf); sumf+=f; e[i][2]-=f;e[i^1][2]+=f; minf-=f; } } if(!sumf)lev[u]=-1; return sumf; } int dinic() { int sum=0; while(bfs()) { sum+=dfs(ss,inf); } return sum; } int hasv[maxv]; void init() { allsumm=allsumn=nume=0; scanf("%d%d",&n,&m); ss=n+m;tt=n+m+1; for(int i=0;i<=tt;i++) { head[i]=-1; hasv[i]=0; } } void read_build() { int temps=0; for(int i=0;i<n;i++) { scanf("%d",&temps); allsumn+=temps; adde(ss,i,temps); for(int j=0;j<m;j++) adde(i,j+n,9); } for(int j=0;j<m;j++) { scanf("%d",&temps); allsumm+=temps; adde(j+n,tt,temps); } } bool dfs_getother_ans(int u,int fa) { if(hasv[u])return 0; for(int i=head[u];i!=-1;i=e[i][1]) { int v=e[i][0]; if(v==fa||e[i][2]<=0||v==ss||v==tt)continue; if(!vis[v]) { vis[v]=1; if(dfs_getother_ans(v,u))return 1; vis[v]=0; //有向图的环出来的时候标记回来啊! } else { return 1; } e[i][2]=0; //删除边!-50ms } hasv[u]=1; //删除点,关键!-900ms return 0; } int main() { int T; scanf("%d",&T); for(int ii=1;ii<=T;ii++) { init(); read_build(); printf("Case #%d: ",ii); if(allsumm!=allsumn) {printf("So naive!\n");continue;} int ans=dinic(); if(ans!=allsumm) { printf("So naive!\n"); } else { flag=0; for(int i=0;i<n;i++) { vis[i]=1; if(dfs_getother_ans(i,-1)) { flag=1; break; } vis[i]=0; } if(flag) printf("So young!\n"); else { printf("So simple!\n"); } } } return 0; }
hdu 4975 最大流及其唯一性判定(有向图环判断算法升级)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。