Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register
欢迎参加IJCAI 2020麻将智能体竞赛,大奖等你拿!Welcome to IJCAI 2020 Mahjong AI competition with amazing prizes! | 北京大学《ACM/ICPC大学生程序设计竞赛训练》暑期课面向全球招生!

为什么连样例也过不了?纠结了2天了,求大牛来看一下

Posted by lyw_sLittleHao at 2013-02-06 20:36:50 on Problem 1459
按刘汝佳训练指南写的Dinic
#include<cstdio>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define N 100+20
#define pb push_back
struct edge{int from,to,cap,flow;};
vector<int>G[N];
vector<edge>E;
int cur[N],d[N],ps,pt;
void add(int a,int b,int c){
  E.pb((edge){a,b,c,0});E.pb((edge){b,a,0,0});
  int si=E.size();
  G[a].pb(si-2);G[b].pb(si-1);
}
bool bfs(){
  int x,f=-1,r=0,i;static int Q[N];Q[0]=ps;
  memset(d,-1,sizeof(d));d[ps]=0;
  while(f!=r){x=Q[++f];
    for(i=0;i<G[x].size();i++){edge&e=E[G[x][i]];
      if(d[e.to]==-1&&e.cap>e.flow){Q[++r]=e.to;d[e.to]=d[x]+1;}
    }
  }
  return d[pt]!=-1;
}
int dfs(int x,int a){
  if(x==pt||a==0)return a;
  int flow=0,f;
  for(int&i=cur[x];i<G[x].size();i++){edge&e=E[G[x][i]];
    if(d[x]+1==d[e.to]&&(f=dfs(e.to,min(a,e.cap-e.flow))>0)){
      e.flow+=f;E[G[x][i]^1].flow-=f;a-=f;flow+=f;
      if(a==0)break;
    }
  }
  return flow;
}
int main(){
    freopen("1459.in","r",stdin);
  freopen("1459.out","w",stdout);
  int i,n,np,nc,m,ans,a,b,c;
  while(scanf("%d%d%d%d",&n,&np,&nc,&m)==4){
    ps=n;pt=n+1;n+=2;
    ans=0;E.clear();for(i=0;i<N;i++)G[i].clear();
    while(m--){scanf(" (%d,%d)%d",&a,&b,&c);add(a,b,c);}
    while(np--){scanf(" (%d)%d",&b,&c);add(ps,b,c);}
    while(nc--){scanf(" (%d)%d",&a,&c);add(a,pt,c);}
    while(bfs()){
      memset(cur,0,sizeof(cur));
      ans+=dfs(ps,100000000);
    }
    printf("%d\n",ans);
  }
  return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator