[关闭]
@zzzc18 2018-01-18T07:41:28.000000Z 字数 5062 阅读 564

Variable变量——二元关系

网络流


变量(variable)

【题目描述】

有n个变量w1~w[n],每个变量可以取W或-W。

有p个式子,形如

有q个条件,形如w[x]<=w[y]或w[x]=w[y]或w[x]

最小化

【输入数据】

第一行一个整数t表示数据组数。

每组数据第一行四个整数n,W,p,q表示节点数。

接下来p行每行九个整数xi,yi,zi,ai,bi,ci,di,ei,fi。

接下来q行每行三个整数x,y,r。

r=0表示w[x]<=w[y];r=1表示w[x]=w[y];r=2表示w[x]

保证存在方案。

【输出数据】

每组数据输出一行一个整数表示的最小值。

【样例输入】

1

3 1 1 1

1 2 3 1 1 1 1 1 1 

1 2 2

【样例输出】

3

【数据范围】

对于30%的数据,n<=15,p,q<=20。

对于100%的数据,t<=10,n<=500,p,q<=1000。

Solution:

首先,由计算 的式子可以发现两点,只有 等取不同的值时,才会对 产生影响;W只是一个系数,可以直接提出来最后算,变量的值为

这个题满足一个二元关系的形式。


二元关系:

例如:有n个任务,可以选择A任务或者B任务,代价分别是a,b,还有一些三元组关系,[x,y,z]表示如果x任务和y任务选的任务不同,将会有一个额外的代价z,现在分配任务,使总代价最小。

image_1c441t7e314eh1uae1ogf10881nt09.png-24.5kB
图片来源

上面这个图是一个流网络,连到 的点表示选择 任务,连到 的点表示选择 任务,其实很形象。
如果要割断 有两类方法:
1.同时割掉 或同时割掉
2.割掉 以及中间的 ,或者割掉 以及中间的

方案1.就表示 相同,没有额外代价
方案2.就表示 不同,有额外代价

(就说这么多吧,足够这个题了,详见上方的图片来源)


为例(已经将 提出)
1.如果 取不同的值时,答案一定会增加(哪怕增加
2.如果 ,没有绝对值得部分对答案的贡献为 ,同理当 时对答案的贡献为

由上面的二元关系,直接就可以建图出来。

image_1c442o6r18jh1pnb1in01shk1i4mm.png-19.9kB

题目中还有一些其他限制
1.对于 ,连 边权为 ,连 边权为 。表示 必须取 , 必须取 (不然网络割不断)
2.对于 ,连 ,边权为
3.对于 ,连,边权为

最后跑最小割即可

注:

1.不要忘了答案最后要乘 W
2.对于负边权,没法跑最小割,有两种解决方法,一种把建图方式改一改,另一种直接把连到 S,T 的边权加上 OFFSET,最后最小割减去 n*OFFSET

  1. //OFFSET法
  2. #include<cmath>
  3. #include<queue>
  4. #include<cstdio>
  5. #include<cstring>
  6. #include<algorithm>
  7. using namespace std;
  8. typedef long long LL;
  9. const int MAXN = 500+9;
  10. int n,W,p,q;
  11. LL val[MAXN];
  12. const LL INF = 2000000000000000LL;
  13. const LL OFFSET = 10000000000LL;
  14. int S,T;
  15. struct E{
  16. int next,to;
  17. LL val;
  18. }edge[MAXN*MAXN*20];
  19. int head[MAXN],iter[MAXN];
  20. int edge_num;
  21. int depth[MAXN];
  22. void addedge(int x,int y,LL val){
  23. edge[++edge_num].next=head[x];
  24. edge[edge_num].to=y;
  25. edge[edge_num].val=val;
  26. head[x]=edge_num;
  27. }
  28. void link(int x,int y,LL val){
  29. addedge(x,y,val);
  30. addedge(y,x,0);
  31. }
  32. void Clean_Edge(){
  33. memset(head,0,sizeof(head));
  34. edge_num=1;
  35. }
  36. bool BFS(int s,int t){
  37. static queue<int> que;
  38. que.push(s);
  39. memset(depth,-1,sizeof(depth));
  40. depth[s]=1;
  41. while(!que.empty()){
  42. int fro=que.front();que.pop();
  43. for(int i=head[fro];i;i=edge[i].next){
  44. if(edge[i].val>0 && depth[edge[i].to]==-1){
  45. depth[edge[i].to]=depth[fro]+1;
  46. que.push(edge[i].to);
  47. }
  48. }
  49. }
  50. return depth[t]!=-1;
  51. }
  52. LL DFS(int x,int goal,LL val){
  53. if(x==goal){
  54. return val;
  55. }
  56. for(int &i=iter[x];i;i=edge[i].next){
  57. if(edge[i].val>0 && depth[edge[i].to]==depth[x]+1){
  58. LL tmp=DFS(edge[i].to,goal,min(val,edge[i].val));
  59. if(tmp>0){
  60. edge[i].val-=tmp;
  61. edge[i^1].val+=tmp;
  62. return tmp;
  63. }
  64. }
  65. }
  66. return 0;
  67. }
  68. LL Dinic(int s,int t){
  69. LL re=0;
  70. while(BFS(s,t)){
  71. memcpy(iter,head,sizeof(head));
  72. while(true){
  73. LL tmp=DFS(s,t,INF);
  74. if(tmp==0)break;
  75. re+=tmp;
  76. }
  77. }
  78. return re;
  79. }
  80. int main(){
  81. /*solution:blog.csdn.net/u011056504/article/details/78997980*/
  82. freopen("variable.in","r",stdin);
  83. freopen("variable.out","w",stdout);
  84. int kase;
  85. scanf("%d",&kase);
  86. while(kase--){
  87. scanf("%d%d%d%d",&n,&W,&p,&q);
  88. S=0;T=n+1;
  89. for(int i=1;i<=n;i++)
  90. val[i]=0;
  91. Clean_Edge();
  92. for(int i=1;i<=p;i++){
  93. int x,y,z,a,b,c,d,e,f;
  94. scanf("%d%d%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&d,&e,&f);
  95. link(x,y,2*a);link(y,x,2*a);
  96. link(y,z,2*b);link(z,y,2*b);
  97. link(x,z,2*c);link(z,x,2*c);
  98. val[x]+=d-f;
  99. val[y]+=e-d;
  100. val[z]+=f-e;
  101. }
  102. for(int i=1;i<=q;i++){
  103. int x,y,r;
  104. scanf("%d%d%d",&x,&y,&r);
  105. if(r==0)
  106. link(x,y,INF);
  107. if(r==1){
  108. link(x,y,INF);
  109. link(y,x,INF);
  110. }
  111. if(r==2){
  112. link(x,T,INF);
  113. link(S,y,INF);
  114. }
  115. }
  116. LL ans=0;
  117. for(int i=1;i<=n;i++){
  118. link(S,i,-val[i]-1+OFFSET);
  119. link(i,T,val[i]+1+OFFSET);
  120. }
  121. ans=Dinic(S,T);
  122. printf("%lld\n",(ans-n*OFFSET)*W);
  123. }
  124. return 0;
  125. }

  1. //另一种方法
  2. #include<queue>
  3. #include<cstdio>
  4. #include<cstring>
  5. #include<algorithm>
  6. #include<cmath>
  7. #define inf 1e9
  8. #define L long long
  9. using namespace std;
  10. const int MaxV = 510, MaxE = 20010;
  11. namespace dinic{
  12. struct edge{
  13. int to, nxt, cap;
  14. }e[MaxE]; int cnt = 1, lst[MaxV];
  15. void ins(int a, int b, int c){ e[++cnt] = (edge){b, lst[a], c}; lst[a] = cnt;}
  16. void lnk(int a, int b, int c){ ins(a, b, c); ins(b, a, 0);}
  17. int h[MaxV]; queue<int>q;
  18. bool bfs(int s, int t){
  19. memset(h, -1, sizeof(h));
  20. h[s] = 0; q.push(s);
  21. while(!q.empty()){
  22. int c = q.front(); q.pop();
  23. for(int i=lst[c], b; b = e[i].to, i; i = e[i].nxt){
  24. if(!~h[b] && e[i].cap > 0){
  25. h[b] = h[c] + 1;
  26. q.push(b);
  27. }
  28. }
  29. }
  30. return ~h[t];
  31. }
  32. int dfs(int v, int t, int f){
  33. if(v == t) return f;
  34. int used = 0, w;
  35. for(int i = lst[v], b; b = e[i].to, i; i = e[i].nxt)
  36. if(h[b] > h[v] && e[i].cap > 0){
  37. w = dfs(b, t, min(f - used, e[i].cap));
  38. e[i].cap -= w; e[i ^ 1].cap += w;
  39. if((used += w) == f) return f;
  40. }
  41. if(!used) h[v] = -1;
  42. return used;
  43. }
  44. int max_flow(int s, int t){
  45. int ans = 0;
  46. while(bfs(s, t))
  47. {
  48. int k=dfs(s, t, 1e9);
  49. if(k>1e8)
  50. return -1;
  51. ans += k;
  52. }
  53. return ans;
  54. }
  55. void clear()
  56. {
  57. memset(lst, 0, sizeof(lst)), cnt = 1;
  58. }
  59. }
  60. using dinic::lnk;
  61. using dinic::max_flow;
  62. using dinic::clear;
  63. int t,n,m,p,q,x,y,z,a,b,c,d,e,f,u[510],ans;
  64. int main()
  65. {
  66. freopen("variable.in","r",stdin);
  67. //freopen("variable.out","w",stdout);
  68. int i;
  69. scanf("%d",&t);
  70. while(t--)
  71. {
  72. scanf("%d%d%d%d",&n,&m,&p,&q);
  73. for(i=1;i<=n;i++)
  74. u[i]=1;
  75. for(i=1;i<=p;i++)
  76. {
  77. scanf("%d%d%d%d%d%d%d%d%d",&x,&y,&z,&a,&b,&c,&d,&e,&f);
  78. lnk(x,y,2*a);
  79. lnk(y,x,2*a);
  80. lnk(y,z,2*b);
  81. lnk(z,y,2*b);
  82. lnk(x,z,2*c);
  83. lnk(z,x,2*c);
  84. u[x]+=d-f;
  85. u[y]+=e-d;
  86. u[z]+=f-e;
  87. }
  88. for(i=1;i<=q;i++)
  89. {
  90. scanf("%d%d%d",&x,&y,&z);
  91. if(z==1)
  92. {
  93. lnk(x,y,inf);
  94. lnk(y,x,inf);
  95. }
  96. else if(z==2)
  97. {
  98. lnk(x,n+1,inf);
  99. lnk(0,y,inf);
  100. }
  101. else
  102. lnk(x,y,inf);
  103. }
  104. for(i=1;i<=n;i++)
  105. {
  106. ans-=abs(u[i]);
  107. if(u[i]>0)
  108. lnk(i,n+1,2*u[i]);
  109. else if(u[i]<0)
  110. lnk(0,i,-2*u[i]);
  111. }
  112. for(int i=2;i<=dinic::cnt;i++)
  113. printf("%d %d\n",dinic::e[i].to,dinic::e[i].cap);
  114. ans+=max_flow(0,n+1);
  115. printf("%lld\n",(L)ans*m);
  116. ans=0;
  117. clear();
  118. }
  119. return 0;
  120. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注