注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

POJ1637 混和图的欧拉回路  

2012-08-15 17:04:40|  分类: POJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
我的算法是网络流,算法与正统的求法并不相同
用的是上下界网络流的思路

#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;

const int MAX=1000*10;
const int INF=1000000000;

struct Edge
{
int s,t,flow,c,next;
}e[MAX];
int begin[MAX],tot;

int n,m,in[MAX],x[MAX],y[MAX],kind[MAX],w[MAX],S,T;

void add(int x,int y,int c)
{
e[tot].t=y;
e[tot].next=begin[x];
begin[x]=tot;
e[tot].flow=0;
e[tot].c=c;
tot++;
}

void addedge(int x,int y,int c)
{
add(x,y,c);
add(y,x,0);
}

int gap[MAX],h[MAX];

int sap(int u,int flow)
{
if(u==T)
return flow;
int i,v,remain=flow,temp;
for(i=begin[u];i!=-1;i=e[i].next)
{
v=e[i].t;
if(h[v]+1==h[u] && e[i].c>e[i].flow)
{
temp=min(e[i].c-e[i].flow,remain);
temp=sap(v,temp);
e[i].flow+=temp;
e[i^1].flow-=temp;
remain-=temp;
if(!remain)
return flow;
}
}
gap[h[u]]--;
if(!gap[h[u]])h[S]=T+1;
h[u]++;
gap[h[u]]++;
return flow-remain;
}

int Main()
{
tot=0;
memset(in,0,sizeof in);
memset(begin,-1,sizeof begin);
memset(gap,0,sizeof gap);
memset(h,0,sizeof h);
memset(w,0,sizeof w);
int i,a,b,w1,all=0;
scanf("%d %d",&n,&m);
S=n+1,T=n+2;
for(i=1;i<=m;++i)
{
scanf("%d %d %d",&a,&b,&w1);
++in[a],++in[b];
x[i]=a;y[i]=b;
if(w1)kind[i]=1;
else kind[i]=0;
}
for(i=1;i<=n;++i)
if(in[i]%2==1)
{
printf("impossible\n");
return 0;
}
for(i=1;i<=m;++i)
if(kind[i]==1)
{
--w[x[i]];
++w[y[i]];
}
else if(kind[i]==-1)
{
++w[x[i]];
--w[y[i]];
}
else
{
addedge(x[i],y[i],1);
addedge(y[i],x[i],1);
}
for(i=1;i<=n;++i)
if(w[i]<0)
{
addedge(i,T,-w[i]);
}
else
{
addedge(S,i,w[i]);
all+=w[i];
}
int ans=0;
gap[0]=T;
while(h[S]<T+1)
ans+=sap(S,INF);
if(ans>=all)
{
printf("possible\n");
}else printf("impossible\n");
return 0;
}

int main()
{
freopen("GK.in","r",stdin);freopen("GK.out","w",stdout);
int Test;
scanf("%d ",&Test);
while(Test--)
Main();
}



  评论这张
 
阅读(213)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018