网络流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;}

1楼ACM_cxlove55分钟前

给跪。。。连个题号都没。。。

Re: zz_121554分钟前

回复ACM_cxloven西南科技大学。。那上面连数据范围都没的。。nhttp://220.166.52.162/oj/searchproblem?sstr=%CF%DF%D0%D4%B9%E6%BB%AE%BA%CD%CD%F8%C2%E7%C1%F724%CC%E2&manner=2