The Fourth Dimension Space

枯叶北风寒,忽然年以残,念往昔,语默心酸。二十光阴无一物,韶光贱,寐难安; 不畏形影单,道途阻且慢,哪曲折,如渡飞湍。斩浪劈波酬壮志,同把酒,共言欢! -如梦令

求SGU 194即ZOJ 2314题AC代码

最近在搞网络流,刚研究完几个求最大流的基本算法,今天研究了一下有上下界的可行流问题,参考了大牛ADN.cn的图论总结,算法倒不是很难,代码也很快就写好了,只是不知道原因,就是不能AC,郁闷我一晚上。。。在SGU上 只能过9组数据,也不知道被什么BT的数据给卡住了,希望大牛们能给我点指点。 我用的方法是添加两个附加源汇,用dinic算法求最大流,如果源汇上的边满流,则说明有可行流,输出每条边的流量,否则输出NO.

下面是我WA掉的代码:
#include<iostream>
#include
<cmath>
#include
<algorithm>
#include
<cstdio>
#include
<cstring>
#include
<cassert>
using namespace std;
#define MAX 210
#define MAXINT 999999999

struct pipe
{
    
    __int64 a;
    __int64 b;
    __int64 l;
    __int64 r;
}
mypipe[MAX*1000];

__int64 n,m;
__int64 graph[MAX][MAX];
__int64 d[MAX];
__int64 ans
=0;

__int64 min(__int64 a,__int64 b)
{
    
    
if(a<b)
        
return a;
    
else
        
return b;
}


void init()
{
    
    __int64 i;
    memset(graph,
0,sizeof(graph));
    
    
for(i=1;i<=m;i++)
    
{
        scanf(
"%I64d%I64d%I64d%I64d",&mypipe[i].a,&mypipe[i].b,&mypipe[i].l,&mypipe[i].r);
        graph[mypipe[i].a][mypipe[i].b]
+=mypipe[i].r-mypipe[i].l;
        graph[mypipe[i].a][n
+2]+=mypipe[i].l;
        graph[n
+1][mypipe[i].b]+=mypipe[i].l;
    }

}

bool build(__int64 n)
{
    
    memset(d,
0,sizeof(d));
    
bool visit[MAX]={0};
    __int64 myqueue[MAX
*MAX]={0};
    
    __int64 front
=1,rear=1;
    myqueue[rear]
=n-1;visit[myqueue[front]]=true;
    
while(front<=rear) 
    
{
        
        __int64 i;
        
for(i=1;i<=n;i++)
        
{
            
if((!visit[i])&&graph[myqueue[front]][i]>0)
            
{
                rear
++;
                myqueue[rear]
=i;
                d[i]
=d[myqueue[front]]+1;
                visit[i]
=true;
                
            }

        }

        
        front
++;
    }

    
if(visit[n]==true)
        
return true;
    
else
        
return false;
}


__int64 dinic(__int64 v,__int64 sum,__int64 n)
{
    
if(v==n)
        
return sum;
    __int64 ret
=0;
    __int64 t;
    __int64 i;
    
for(i=1;i<=n;i++)
    
{
        
if(d[i]==d[v]+1&&graph[v][i]>0)
        

            t
=dinic(i,min(graph[v][i],sum)-ret,n);
            graph[v][i]
-=t; 
            graph[i][v]
+=t;
            ret
+=t;
        }

    }
 
    
return ret;
}



int main()
{
    
    __int64 j;
    __int64 flag
=0;
    
    
    
while(scanf("%I64d%I64d",&n,&m)!=EOF)
    
{

        
        
        init();
        flag
=0;
        
while(build(n+2))
        
{
            dinic(n
+1,MAXINT,n+2);
        }

        
for(j=1;j<=n;j++)
        
{
            
            
if(graph[j][n+2]!=0||graph[n+1][j]!=0)
            
{
                
                flag
=1;
                
break;
            }

        }

        
if(flag==1)
        
{
            printf(
"NO\n\n");
            
continue;
        }

        
else
        
{
            printf(
"YES\n");
            
for(j=1;j<=m;j++)
            
{
                
                printf(
"%I64d\n",graph[mypipe[j].b][mypipe[j].a]+mypipe[j].l);
            }

            printf(
"\n");
        }

        
    }

    
return 0;
}
 

posted on 2009-07-12 01:58 abilitytao 阅读(555) 评论(2)  编辑 收藏 引用

评论

# re: 求SGU 194即ZOJ 2314题AC代码 2009-09-04 17:25 402158021@qq.com

可能是dinic有问题
给你我的代码
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cmath>
#include<string>
#include<queue>
#include<string.h>

using namespace std;

int map[300][300];
int start,end,en,vn;
int path[300],flow[300];
int maxf=0;

struct Pipe
{
int px,py,pl,pc;
}pipe[1000000];

int bfs()
{
int i,j,k;
int cur=0;
memset(path,-1,sizeof(path));
memset(flow,0,sizeof(flow));

path[start]=start;
flow[start]=0x0fffffff;

queue<int> q;
q.push(start);
while(!q.empty())
{
cur=q.front();
// printf("cur=%d\tend=%d\n",cur,end);
q.pop();
if(cur==end)break;
// printf("vn=%d\n",vn);
for(i=0;i<vn;i++)
{
// printf("11111\n");
if(path[i]==-1&&map[cur][i])
{
path[i]=cur;
q.push(i);
flow[i]=flow[cur]<map[cur][i]?flow[cur]:map[cur][i];
}
}
}
// printf("fff=%d\n",flow[end]);
if(path[end]==-1)return -1;
return flow[end];
}


int maxflow()
{
int i,j,k;
int pre,cur;
while(1)
{
k=bfs();
if(k==-1)break;
maxf+=k;
cur=end;
while(cur!=start)
{
pre=path[cur];
map[pre][cur]-=k;
map[cur][pre]+=k;
cur=pre;
}
}
return maxf;
}

int main()
{
int i,j,k;
while(scanf("%d %d",&vn,&en)!=EOF)
{
memset(map,0,sizeof(map));
memset(pipe,0,sizeof(pipe));
maxf=0;
start=0;end=vn+1;
for(i=0;i<en;i++)
{
scanf("%d%d%d%d",&pipe[i].px,&pipe[i].py,&pipe[i].pl,&pipe[i].pc);
map[pipe[i].px][pipe[i].py]+=pipe[i].pc-pipe[i].pl;
map[start][pipe[i].py]+=pipe[i].pl;
map[pipe[i].px][end]+=pipe[i].pl;
}
vn+=2;
k=maxflow();
int ok=1;
for(i=0;i<en;i++)
{
if(map[start][pipe[i].py]!=0||map[pipe[i].px][end]!=0)
{
ok=0;break;
}
}
if(!ok)
printf("NO\n");
else
{
printf("YES\n");
for(i=0;i<en;i++)
printf("%d\n",map[pipe[i].py][pipe[i].px]+pipe[i].pl);
}
}
return 0;
}


  回复  更多评论   

# re: 求SGU 194即ZOJ 2314题AC代码 2009-09-04 18:01 abilitytao

@402158021@qq.com
多谢^_^  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理