二分最小割。
一個答案可行要滿足$ v-c*ans \leq 0 $
将S向每個點連邊,流量為該點權值,相鄰兩個點連邊,流量為邊的費用*ans,邊界上的點向邊界外面連邊,流量也為相應費用*ans。
可以發現,每一種割完連到S的點都是選了的點,選了的點和未選的點中間的邊的費用一定割了,未選的點的權值也沒有得到,是以是正确的。
這樣會不會有不滿足條件的情況呢?
答案是否定的,如果圈了兩個圈,那麼肯定有一個圈大一個圈小,那麼往上二分時一定是隻選大的更優。
1 #include<cstdio>
2 #include<cstring>
3 #include<iostream>
4 #include<algorithm>
5 #include<cmath>
6 #include<queue>
7 #define N 2550
8 #define inf 0x7fffffff
9 #define eps 1e-8
10 using namespace std;
11 int n,m,S,T,a[55][55],b[55][55],c[55][55];
12 double sum;
13 int id(int i,int j){
14 if(!i||!j||i>n||j>m)return T;
15 return (i-1)*m+j;
16 }
17 int e=2,head[N];
18 struct edge{
19 int u,v,next;
20 double f,r;
21 }ed[N<<4];
22 void add(int u,int v,double f){
23 ed[e].u=u;ed[e].v=v;ed[e].f=ed[e].r=f;
24 ed[e].next=head[u];head[u]=e++;
25 ed[e].u=v;ed[e].v=u;ed[e].f=ed[e].r=0;
26 ed[e].next=head[v];head[v]=e++;
27 }
28 int dep[N];
29 bool bfs(){
30 memset(dep,0,sizeof dep);
31 queue<int> Q;
32 Q.push(S);dep[S]=1;
33 while(!Q.empty()){
34 int x=Q.front();Q.pop();
35 for(int i=head[x];i;i=ed[i].next){
36 if(ed[i].f>0&&!dep[ed[i].v]){
37 dep[ed[i].v]=dep[x]+1;
38 if(ed[i].v==T)return 1;
39 Q.push(ed[i].v);
40 }
41 }
42 }
43 return 0;
44 }
45 double dfs(int x,double f){
46 if(x==T||f==0)return f;
47 double ans=0;
48 for(int i=head[x];i;i=ed[i].next){
49 if(ed[i].f>0&&dep[ed[i].v]==dep[x]+1){
50 double nxt=dfs(ed[i].v,min(ed[i].f,f));
51 ans+=nxt;f-=nxt;ed[i].f-=nxt;ed[i^1].f+=nxt;
52 }
53 if(f==0)break;
54 }
55 if(ans==0)dep[x]=-1;
56 return ans;
57 }
58 double dinic(){
59 double ans=0;
60 while(bfs())ans+=dfs(S,inf);
61 return ans;
62 }
63 bool work(double x){
64 for(int i=2;i<e;i++)
65 if(ed[i].u==S)ed[i].f=ed[i].r;
66 else ed[i].f=x*ed[i].r;
67 double ans=dinic();
68 return sum-ans>0;
69 }
70 int main(){
71 scanf("%d%d",&n,&m);
72 S=n*m+1;T=S+1;
73 for(int i=1;i<=n;i++)
74 for(int j=1;j<=m;j++)scanf("%d",&a[i][j]),sum+=a[i][j];
75 for(int i=1;i<=n+1;i++)
76 for(int j=1;j<=m;j++)scanf("%d",&b[i][j]);
77 for(int i=1;i<=n;i++)
78 for(int j=1;j<=m+1;j++)scanf("%d",&c[i][j]);
79 for(int i=1;i<=n;i++){
80 for(int j=1;j<=m;j++){
81 add(S,id(i,j),a[i][j]);
82 add(id(i,j),id(i-1,j),b[i][j]);
83 add(id(i,j),id(i,j-1),c[i][j]);
84 add(id(i,j),id(i+1,j),b[i+1][j]);
85 add(id(i,j),id(i,j+1),c[i][j+1]);
86 }
87 }
88 double l=0,r=1255,mid,ans;
89 while(r-l>eps){
90 mid=(l+r)/2.0;
91 if(work(mid))l=ans=mid;
92 else r=mid;
93 }
94 printf("%0.3lf\n",ans);
95 return 0;
96 }
View Code
還有一種費用流的算法,可以通過判負環來判斷解是否可行,是把每個交點看作每個點
一個點往右連時的邊權就是這條邊下面的點權和-這條邊的費用,往左連就是反過來把下面的删去,往上下走隻要加上邊的費用即可
然後就可以愉快的spfa了!
轉載于:https://www.cnblogs.com/Ren-Ivan/p/8297502.html