首页 > 代码库 > Energy Minimization

Energy Minimization

2024-07-21 06:51:56   216人阅读

zoj2539:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2539

题意：公式第一项只要当xi=0时才会有作用，第二项只有当xi=1时才会有作用，第三项只有当xi和xj不相等时才会有作用

题解：对于每个点i,xi要么等于0，要么等于1，即点i要么属于S集，要么属于T集，如果点i,j不在同一个集合，它们之间会产生附加值总的最小value值正好对应一个最小割的容量，value=http://www.mamicode.com/Sum(v0i)+Sum(v1j)+Sum(vij),令v0为源点，v1为汇点，则i表示点i属于S集，点j表示j属于T集，当(s,i)为割边时，(i,t)不会是割边，同理，（i,t）为割边时，(s,i)不会是割边，当i,j在同一个集合时，（i,j）不会是割边。所以只要充分理解了最小割，就知道为什么跑了一遍最大流就能够搞定了。

  1 #include<iostream>  2 #include<cstring>  3 #include<algorithm>  4 #include<cstdio>  5 #include<queue>  6 #define INF 100000000  7 using namespace std;  8 const int N=402;  9 const int M=820; 10 struct Node{ 11    int v; 12    int f; 13    int next; 14 }edge[M]; 15 int n,m,u,v,cnt,sx,ex; 16 int head[N],pre[N]; 17 int mp[21][21];//根据题目要求申请 18 void init(){ 19     cnt=0; 20     memset(head,-1,sizeof(head)); 21 } 22 void add(int u,int v,int w){ 23     edge[cnt].v=v; 24     edge[cnt].f=w; 25     edge[cnt].next=head[u]; 26     head[u]=cnt++; 27     edge[cnt].f=0; 28     edge[cnt].v=u; 29     edge[cnt].next=head[v]; 30     head[v]=cnt++; 31 } 32 bool BFS(){ 33   memset(pre,0,sizeof(pre)); 34   pre[sx]=1; 35   queue<int>Q; 36   Q.push(sx); 37  while(!Q.empty()){ 38      int d=Q.front(); 39      Q.pop(); 40      for(int i=head[d];i!=-1;i=edge[i].next    ){ 41         if(edge[i].f&&!pre[edge[i].v]){ 42             pre[edge[i].v]=pre[d]+1; 43             Q.push(edge[i].v); 44         } 45      } 46   } 47  return pre[ex]>0; 48 } 49 int dinic(int flow,int ps){ 50     int f=flow; 51      if(ps==ex)return f; 52      for(int i=head[ps];i!=-1;i=edge[i].next){ 53         if(edge[i].f&&pre[edge[i].v]==pre[ps]+1){ 54             int a=edge[i].f; 55             int t=dinic(min(a,flow),edge[i].v); 56               edge[i].f-=t; 57               edge[i^1].f+=t; 58             flow-=t; 59              if(flow<=0)break; 60         } 61  62      } 63       if(f-flow<=0)pre[ps]=-1; 64       return f-flow; 65 } 66 int solve(){ 67     int sum=0; 68     while(BFS()) 69         sum+=dinic(INF,sx); 70     return sum; 71 } 72 int main() { 73     int T,k,temp,sum,v0,v1,tt=1; 74     scanf("%d",&T); 75     while(T--) { 76          scanf("%d%d%d%d",&n,&m,&v0,&v1); 77          init(); 78          for(int i=1;i<=n;i++){ 79             for(int j=1;j<=m;j++){ 80                  scanf("%d",&mp[i][j]); 81             } 82          } 83          for(int i=1;i<=n;i++){ 84             for(int j=1;j<=m;j++){ 85                 int a=(i-1)*m+j; 86               add(0,a,abs(mp[i][j]-v0)); 87               add(a,n*m+1,abs(mp[i][j]-v1)); 88                 if(i<n){ 89                     int b=a+m; 90                     add(a,b,abs(mp[i][j]-mp[i+1][j])); 91                     add(b,a,abs(mp[i][j]-mp[i+1][j])); 92                 } 93                 if(j<m){ 94                     int b=a+1; 95                     add(a,b,abs(mp[i][j]-mp[i][j+1])); 96                     add(b,a,abs(mp[i][j]-mp[i][j+1])); 97                 } 98             } 99          }100          sx=0,ex=n*m+1;101           if(tt>1)puts("");102        printf("Case %d:\n%d\n",tt++,solve());103     }104     return 0;105 }
View Code

 

Energy Minimization


联系
我们