网络流24题
01
#pragma comment(linker, "/STACK:102400000,102400000")#include<iostream>#include<vector>#include<algorithm>#include<cstdio>#include<queue>#include<stack>#include<string>#include<map>#include<set>#include<cmath>#include<cassert>#include<cstring>#include<iomanip>using namespace std;#ifdef _WIN32#define i64 __int64#define out64 "%I64d\n"#define in64 "%I64d"#else#define i64 long long#define out64 "%lld\n"#define in64 "%lld"#endif/************ for topcoder by zz1215 *******************/#define FOR(i,a,b) for( int i = (a) ; i <= (b) ; i ++)#define FF(i,a) for( int i = 0 ; i < (a) ; i ++)#define FFD(i,a,b) for( int i = (a) ; i >= (b) ; i --)#define S64(a) scanf(in64,&a)#define SS(a) scanf("%d",&a)#define LL(a) ((a)<<1)#define RR(a) (((a)<<1)+1)#define pb push_back#define pf push_front#define X first#define Y second#define CL(Q) while(!Q.empty())Q.pop()#define MM(name,what) memset(name,what,sizeof(name))#define MC(a,b) memcpy(a,b,sizeof(b))#define MAX(a,b) ((a)>(b)?(a):(b))#define MIN(a,b) ((a)<(b)?(a):(b))#define read freopen("in.txt","r",stdin)#define write freopen("out.txt","w",stdout)const int inf = 0x3f3f3f3f;const i64 inf64 = 0x3f3f3f3f3f3f3f3fLL;const double oo = 10e9;const double eps = 10e-9;const double pi = acos(-1.0);const int maxn = 222;const int head = 0;const int end = 221;struct zz{int from;int to;int c;int cost;int id;}zx;vector<zz>g[maxn];int m,n;int a[maxn];bool inq[maxn];int way[maxn];int back[maxn];int f[maxn][maxn];void link(int now,int to,int c,int cost,int bc=0){zx.from = now; zx.to=to; zx.c=c; zx.cost=cost; zx.id=g[zx.to].size();g[zx.from].pb(zx);swap(zx.from,zx.to); zx.c=bc; zx.cost=-cost; zx.id=g[zx.to].size()-1;g[zx.from].pb(zx);return ;}bool spfa(bool x){if(x){for(int i=0;i<maxn;i++){way[i]=-inf;}}else{for(int i=0;i<maxn;i++){way[i]=inf;}}MM(back,-1);queue<int>q;MM(inq,false);inq[head]=true;way[head]=0;q.push(head);int now,to,temp;while(!q.empty()){now = q.front();q.pop();for(int i=0;i<g[now].size();i++){to = g[now][i].to;if(g[now][i].c>0){temp = g[now][i].cost + way[now];if(x){if(temp>way[to]){back[to] = g[now][i].id;way[to]=temp;if(!inq[to]){inq[to]=true;q.push(to);}}}else{if(temp<way[to]){back[to]=g[now][i].id;way[to]=temp;if(!inq[to]){inq[to]=true;q.push(to);}}}}}inq[now]=false;}if(x){return way[end]!=-inf;}else{return way[end]!=inf;}}int dfs(int flow=inf,int to=end){if(to == head) return flow;int now = g[to][back[to]].to;int id = g[to][back[to]].id;int re = dfs(min(flow,g[now][id].c),now);g[now][id].c-=re;g[to][back[to]].c+=re;return re;}int ek(bool x){int ans = 0;while(spfa(x)){ans+=dfs()*way[end];}return ans;}void build(){ for(int i=0;i<maxn;i++){g[i].clear();} for(int i=1;i<=m;i++){link(head,i,a[i],0);}for(int i=m+1;i<=m+n;i++){link(i,end,a[i],0);}int cost;for(int i=1;i<=m;i++){for(int j=m+1;j<=m+n;j++){link(i,j,inf,f[i][j]);}}return ;}int main(){while(cin>>m>>n){for(int i=1;i<=m;i++){cin>>a[i];}for(int i=1+m;i<=n+m;i++){cin>>a[i];}for(int i=1;i<=m;i++){for(int j=m+1;j<=m+n;j++){cin>>f[i][j];}}build();cout<<ek(false)<<endl;build();cout<<ek(true)<<endl;}return 0;}