二分最小割。
一个答案可行要满足$ 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 ",ans); 95 return 0; 96 }
还有一种费用流的算法，可以通过判负环来判断解是否可行，是把每个交点看作每个点
一个点往右连时的边权就是这条边下面的点权和-这条边的费用，往左连就是反过来把下面的删去，往上下走只要加上边的费用即可
然后就可以愉快的spfa了！