hdu3549 网络流

2017年02月24日 10点热度 0人点赞 0条评论
#include
#include
#include
#include
using namespace std;
int pre[1005],s=1,t,g[1005][1005],vis[1005],m;
bool bfs(){
    memset(pre,0,sizeof(pre));
    memset(vis,0,sizeof(vis));
int k;
queue q;
q.push(s);
vis[s]=1;
while(!q.empty()){
    k=q.front();
    if(k==t) return true;
    q.pop();
    for(int i=1;i<=t;i++){
        if(!vis[i]&&g[k][i]){
            pre[i]=k;
            vis[i]=1;
            q.push(i);
        }
    }
}
return false;
}
int maxflow(){
    int ans=0,minn=0x3f3f3f3f;
while(true){
    if(!bfs()) return ans;
    for(int i=t;i!=s;i=pre[i])
            minn=min(minn,g[pre[i]][i]);
            for(int i=t;i!=s;i=pre[i])
                g[pre[i]][i]-=minn,g[i][pre[i]]+=minn;
            ans+=minn;
}
}
int main(){
    //freopen("1.txt","r",stdin);
int num,t1,t2,t3;
cin>>num;
for(int i=1;i<=num;i++){
    cin>>t>>m;
    memset(g,0,sizeof(g));
    printf("Case %d: ",i);
    for(int i=1;i<=m;i++){
        cin>>t1>>t2>>t3;
        g[t1][t2]+=t3;
    }
    cout<

未经允许不得转载!hdu3549 网络流

update

纸上得来终觉浅, 绝知此事须躬行。