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

Yavin(某沙茶的代码库)

Star Wars fan and OIer

 
 
 

日志

 
 

SGU326 我是不会在标题中写算法的  

2012-08-17 14:29:46|  分类: SGU300系列 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
很明显我是被标题坑了的,在搜索翻译时不小心看到了最大流
于是被水掉了了

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

const int NUM=500;
const int INF=100000000;

int n,won[NUM],r[NUM],map[NUM][NUM],cnt,S,T,C[NUM][NUM],f[NUM][NUM],all;
int h[NUM],gap[NUM];

int sap(int u,int flow)
{
if(u==T)
return flow;
int v,remain=flow,temp;
for(v=1;v<=cnt;++v)
if(C[u][v]>f[u][v] && h[v]+1 == h[u])
{
temp=min(C[u][v]-f[u][v],remain);
temp=sap(v,temp);
f[u][v]+=temp;
f[v][u]-=temp;
remain-=temp;
if(!remain)
return flow-remain;
}
gap[h[u]]--;
if(!gap[h[u]])h[S]=cnt+1;
h[u]++;
++gap[h[u]];
return flow-remain;
}

int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);freopen("output.txt","w",stdout);
#endif
int i,aim=0,j;
scanf("%d",&n);
for(i=1;i<=n;++i)
scanf("%d ",&won[i]);
for(i=1;i<=n;++i)
scanf("%d",&r[i]);
all=won[1]+r[1];
S=n+1,T=n+2;
cnt=n+2;
for(i=2;i<=n;++i)
{
C[S][i]=all-won[i];
if(all<won[i])
{
printf("NO\n");
return 0;
}
}
for(i=1;i<=n;++i)
for(j=1;j<=n;++j)
scanf("%d ",&map[i][j]);
for(i=2;i<=n;++i)
for(j=i+1;j<=n;++j)
{
++cnt;
C[j][cnt]=C[i][cnt]=INF;
C[cnt][T]=map[i][j];
aim+=map[i][j];
}
memset(h,0,sizeof h);
memset(gap,0,sizeof gap);
gap[0]=cnt;
int ans=0;
while(h[S]<cnt+1)
ans+=sap(S,INF);
if(ans==aim)
printf("YES\n");
else printf("NO\n");
}



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

历史上的今天

评论

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

页脚

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