[toggle hide="yes" title="题目：BZOJ2039 employee人员雇佣" color=""]2039: [2009国家集训队]employ人员雇佣
Description
作为一个富有经营头脑的富翁，小L决定从本国最优秀的经理中雇佣一些来经营自己的公司。这些经理相互之间合作有一个贡献指数,（我们用Ei,j表示i经理对j经理的了解程度），即当经理i和经理j同时被雇佣时，经理i会对经理j做出贡献，使得所赚得的利润增加Ei,j。当然，雇佣每一个经理都需要花费一定的金钱Ai，对于一些经理可能他做出的贡献不值得他的花费，那么作为一个聪明的人，小L当然不会雇佣他。 然而，那些没有被雇佣的人会被竞争对手所雇佣，这个时候那些人会对你雇佣的经理的工作造成影响，使得所赚得的利润减少Ei,j（注意：这里的Ei,j与上面的Ei,j 是同一个）。 作为一个效率优先的人，小L想雇佣一些人使得净利润最大。你可以帮助小L解决这个问题吗？
Input
第一行有一个整数N<=1000表示经理的个数 第二行有N个整数Ai表示雇佣每个经理需要花费的金钱 接下来的N行中一行包含N个数，表示Ei,j，即经理i对经理j的了解程度。（输入满足Ei,j=Ej,i）
Output
第一行包含一个整数，即所求出的最大值。
Sample Input
3
3 5 100
0 6 1
6 0 2
1 2 0
Sample Output
1
【数据规模和约定】
20%的数据中N<=10
50%的数据中N<=100
100%的数据中 N<=1000， Ei,j<=maxlongint, Ai<=maxlongint[/toggle]
[toggle hide="yes" title="题目：BZOJ2127 happiness" color=""]
Description
高一一班的座位表是个n*m的矩阵，经过一个学期的相处，每个同学和前后左右相邻的同学互相成为了好朋友。这学期要分文理科了，每个同学对于选择文科与理科有着自己的喜悦值，而一对好朋友如果能同时选文科或者理科，那么他们又将收获一些喜悦值。作为计算机竞赛教练的scp大老板，想知道如何分配可以使得全班的喜悦值总和最大。
Input
第一行两个正整数n，m。接下来是六个矩阵第一个矩阵为n行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择文科获得的喜悦值。第二个矩阵为n行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学选择理科获得的喜悦值。第三个矩阵为n-1行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择文科获得的额外喜悦值。第四个矩阵为n-1行m列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i+1行第j列的同学同时选择理科获得的额外喜悦值。第五个矩阵为n行m-1列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择文科获得的额外喜悦值。第六个矩阵为n行m-1列 此矩阵的第i行第j列的数字表示座位在第i行第j列的同学与第i行第j+1列的同学同时选择理科获得的额外喜悦值。
Output
输出一个整数，表示喜悦值总和的最大值
Sample Input
1 2
1 1
100 110
1
1000
Sample Output
1210
【样例说明】
两人都选理，则获得100+110+1000的喜悦值。
【数据规模】
对于100%以内的数据，n,m<=100 所有喜悦值均为小于等于5000的非负整数
[/toggle]
这俩题是最小割的经典模型，即获得一个点的价值后还可能获得其与其他点的“绑定价值”。对于这样的题，可以先考虑仅有一个“限制关系”，即仅有一个获利规则，然后在此基础上继续添加限制条件。利用最小割，可以将“获得利益”转化为“舍弃最小利益”，然后用总获利减去舍弃的，即为获得的最大利益。在构图时，可以先搞个简单的模型，再考虑舍弃掉边后可能出现的情况，结合其实际含义为边赋流量。同时，如果遇到获利关系不好转化的情况，可以拆点、加点（例如happiness，可以拆点将同选文理的获利转成新边，考虑新模型可能出现的割法）。
[toggle hide="yes" title="" color=""]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; inline int read(){ int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar(); return s*f; } #define mxn 1005 #define mxm 4000005 #define inf 1000000000 struct edge{ int v,w,nxt; }e[mxm]; int prv[mxn],tot=1; int S,T,n,m; inline void add(int u,int v,int w){ e[++tot]=(edge){v,w,prv[u]},prv[u]=tot; e[++tot]=(edge){u,0,prv[v]},prv[v]=tot; } int q[mxn],dep[mxn],qh,qt; inline bool bfs(){ memset(dep,0,sizeof(dep)); q[1]=S,dep[S]=1,qh=qt=1; int u; while(qh<=qt){ u=q[qh++]; for(int i=prv[u];i;i=e[i].nxt) if(!dep[e[i].v]&&e[i].w) dep[e[i].v]=dep[u]+1,q[++qt]=e[i].v; if(dep[T]) return 1; } return 0; } int dfs(int u,int fl){ if(u==T||(!fl)) return fl; int ret=0; for(int i=prv[u];i;i=e[i].nxt) if(e[i].w&&dep[e[i].v]==dep[u]+1) { int f=dfs(e[i].v,min(fl,e[i].w)); e[i].w-=f,e[i^1].w+=f; fl-=f,ret+=f; if(!fl) break; } if(!ret) dep[u]=-1; return ret; } inline int dinic(){ int ret=0; while(bfs()) ret+=dfs(S,inf); return ret; } int E[mxn][mxn],a[mxn],ans; int main(){ n=read(); for(int i=1;i<=n;++i) a[i]=read(); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) E[i][j]=read(),ans+=E[i][j]; S=0,T=n+1; for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) if(i!=j) add(i,j,2*E[i][j]),add(S,i,E[i][j]); for(int i=1;i<=n;++i) add(i,T,a[i]); int d=dinic(); cout<<ans-d; } |
[/toggle]
[toggle hide="yes" title="" color=""]
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 |
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; inline int read(){ int s=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();} while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+ch-'0',ch=getchar(); return s*f; } #define mxn 105 #define mxm 3000005 #define inf 1000000000 struct edge{ int v,w,nxt; }e[mxm]; int prv[mxm],tot=1; int S,T,n,m; inline void add(int u,int v,int w){ e[++tot]=(edge){v,w,prv[u]},prv[u]=tot; e[++tot]=(edge){u,0,prv[v]},prv[v]=tot; } inline void add2(int u,int v,int w){ e[++tot]=(edge){v,w,prv[u]},prv[u]=tot; e[++tot]=(edge){u,w,prv[v]},prv[v]=tot; } int q[mxm],dep[mxm],qh,qt; inline bool bfs(){ memset(dep,0,sizeof(dep)); q[1]=S,dep[S]=1,qh=qt=1; int u; while(qh<=qt){ u=q[qh++]; for(int i=prv[u];i;i=e[i].nxt) if(!dep[e[i].v]&&e[i].w) dep[e[i].v]=dep[u]+1,q[++qt]=e[i].v; if(dep[T]) return 1; } return 0; } int dfs(int u,int fl){ if(u==T||(!fl)) return fl; int ret=0; for(int i=prv[u];i;i=e[i].nxt) if(e[i].w&&dep[e[i].v]==dep[u]+1) { int f=dfs(e[i].v,min(fl,e[i].w)); e[i].w-=f,e[i^1].w+=f; fl-=f,ret+=f; if(!fl) break; } if(!ret) dep[u]=-1; return ret; } inline int dinic(){ int ret=0; while(bfs()) ret+=dfs(S,inf); return ret; } int dw[mxn][mxn],dl[mxn][mxn],twud[mxn][mxn],tlud[mxn][mxn],twlr[mxn][mxn],tllr[mxn][mxn],ttl; int idx[mxn][mxn]; int main(){ freopen("nt2011_happiness.in","r",stdin); freopen("nt2011_happiness.out","w",stdout); n=read(),m=read(); for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) dw[i][j]=read(),ttl+=dw[i][j]; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) dl[i][j]=read(),ttl+=dl[i][j]; for(int i=1;i<n;++i) for(int j=1;j<=m;++j) twud[i][j]=read(),ttl+=twud[i][j]; for(int i=1;i<n;++i) for(int j=1;j<=m;++j) tlud[i][j]=read(),ttl+=tlud[i][j]; for(int i=1;i<=n;++i) for(int j=1;j<m;++j) twlr[i][j]=read(),ttl+=twlr[i][j]; for(int i=1;i<=n;++i) for(int j=1;j<m;++j) tllr[i][j]=read(),ttl+=tllr[i][j]; int temp=0; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) idx[i][j]=++temp; ttl*=2; S=n*m+11,T=n*m+10; for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) { add(S,idx[i][j],2*dw[i][j]+twud[i-1][j]+twud[i][j]+twlr[i][j-1]+twlr[i][j]); add(idx[i][j],T,2*dl[i][j]+tlud[i-1][j]+tlud[i][j]+tllr[i][j-1]+tllr[i][j]); if(i<n)add2(idx[i][j],idx[i+1][j],twud[i][j]+tlud[i][j]); if(j<m)add2(idx[i][j],idx[i][j+1],twlr[i][j]+tllr[i][j]); } int d=dinic(); ttl-=d; cout<<ttl/2; } |
[/toggle]
叨叨几句... NOTHING