当前位置: 代码迷 >> 综合 >> POJ 1459 基本输入题英文阅读题
  详细解决方案

POJ 1459 基本输入题英文阅读题

热度:42   发布时间:2024-01-20 20:29:59.0

so.... 输入考验功底啊... 还好,没难倒我~哇哈哈哈~

#include<iostream>
#include<string>
#include<cstdio>
#define MN 111
using namespace std;int n,f,e,d,ans,s,t;
int map[MN][MN],que[MN],a[MN],vis[MN],pre[MN];void setG()
{int i,u,v,c;ans=0;s=n+1;t=n+2;memset( map,0,sizeof(map) );for( i=0;i<e;i++ ){scanf( "\n (%d,%d)%d",&u,&v,&c );//printf( "%d %d %d\n",u,v,c );map[u][v]+=c;}for( i=0;i<f;i++ ){scanf( "\n (%d)%d",&u,&c );//printf( "%d %d\n",u,c );map[s][u]+=c;}for( i=0;i<d;i++ ){scanf( "\n (%d)%d",&u,&c );//printf( "%d %d\n",u,c );map[u][t]+=c;}
}bool bfs()
{memset(vis,0,sizeof(vis));int head=0,foot=0;que[foot++]=s;vis[s]=true;a[s]=INT_MAX;while( head<foot ){int u=que[head++];for( int i=0;i<=t;i++ ){if( !vis[i]&&map[u][i] ){vis[i]=true;que[foot++]=i;a[i]=min( a[u],map[u][i] );pre[i]=u;if( i==t )return true;}}}return false;
}void work()
{int m;while( bfs() ){m=t;ans+=a[t];while( m!=s ){map[pre[m]][m]-=a[t];map[m][pre[m]]+=a[t];m=pre[m];}}printf( "%d\n",ans );
}int main()
{while( scanf("%d%d%d%d",&n,&f,&d,&e)!=EOF ){setG();work();}return 0;
}