心烦意乱的时候调这道题真是... 越调越气, 就这样过了一晚上...
今天再认真看看, 找出几处小错, 就 A 了...
关于题解: https://www.cnblogs.com/CQzhangyu/p/6790404.html
关于最大权闭合子图: http://www.cnblogs.com/wuyiqi/archive/2012/03/12/2391960.HTML
对于这道题, 首先, 可以 01 分数规划, 于是问题变成二分比值后找最大答案;
把每个格子看做一个点, 点之间的边权是格子边上的值 * 二分的比值, 则割掉这条边表示两个点中选一个, 那么自然一内一外, 它们的交界也就成了封闭路线的边界;
把外围看做还有一圈点, 于是边缘的点向汇点连外围边界的值的边;
然后源点向每个点连权值为点 (格子) 权的边, 割这条边表示不要这个点的贡献了;
在这个图上跑最小割, 总点权减去最小割就是答案;
注意 ct = 1 ! 边权要乘二分的比值 k !
代码如下:
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- #include<queue>
- #define eps 1e-6
- #define inf 1e9
- using namespace std;
- int const xn=60,xm=3000,xe=5e4;//
- int n,m,s,t,w[xn][xn],sid[xn][xn][xn][xn],S,T;
- int dis[xm],hd[xm],ct=1,to[xe],nxt[xe],cur[xm];
- int e1[xn][xn],e2[xn][xn];
- double ans,c[xe],sum;
- queue<int>q;
- void add(int x,int y,double z)
- {
- to[++ct]=y; nxt[ct]=hd[x]; c[ct]=z; hd[x]=ct;
- to[++ct]=x; nxt[ct]=hd[y]; c[ct]=0; hd[y]=ct;
- }
- int rd()
- {
- int ret=0,f=1; char ch=getchar();
- while(ch<'0'||ch>'9'){if(ch=='-')f=0; ch=getchar();}
- while(ch>='0'&&ch<='9')ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
- return f?ret:-ret;
- }
- int id(int x,int y){return (x-1)*m+y;}
- int P(int x,int y){return (x-1)*m+y;}
- bool bfs()
- {
- while(q.size())q.pop();
- memset(dis,0,sizeof dis);
- dis[s]=1; q.push(s);
- while(q.size())
- {
- int x=q.front(); q.pop();
- for(int i=hd[x],u;i;i=nxt[i])
- if(!dis[u=to[i]]&&c[i]>eps)dis[u]=dis[x]+1,q.push(u);
- }
- return dis[t];
- }
- double dfs(int x,double fl)
- {
- if(x==t)return fl;
- double ret=0;
- for(int &i=cur[x],u;i;i=nxt[i])
- {
- if(dis[u=to[i]]!=dis[x]+1||c[i]<=eps)continue;
- double tmp=dfs(u,min(fl-ret,c[i]));
- if(tmp<eps)dis[u]=0;
- c[i]-=tmp; c[i^1]+=tmp;
- ret+=tmp; if(fl-ret<eps)return ret;
- }
- return ret;
- }
- bool ck(double k)
- {
- memset(hd,0,sizeof hd); ct=1;//=1 而不是 0 !!!!!!!!!!!!!!!!!!!!!!!
- s=0; t=n*m+1;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- {
- int x=id(i,j);
- add(s,x,w[i][j]);
- if(i==1)add(x,t,sid[i-1][j][i][j]*k);
- if(j==1)add(x,t,sid[i][j-1][i][j]*k);
- if(i==n)add(x,t,sid[i][j][i+1][j]*k);
- if(j==m)add(x,t,sid[i][j][i][j+1]*k);
- int y=id(i+1,j),z=id(i,j+1);
- if(i<n)add(x,y,k*sid[i][j][i+1][j]),add(y,x,k*sid[i][j][i+1][j]);
- if(j<m)add(x,z,k*sid[i][j][i][j+1]),add(z,x,k*sid[i][j][i][j+1]);//k*!!!
- }
- double ans=0;
- while(bfs())
- {
- memcpy(cur,hd,sizeof hd);
- ans+=dfs(0,inf);
- }
- return sum-ans>eps;
- }
- int main()
- {
- n=rd(); m=rd(); s=0; t=n*m+1; double l=0,r=0;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)w[i][j]=rd(),r+=w[i][j],sum+=w[i][j];
- for(int i=1;i<=n+1;i++)
- for(int j=1;j<=m;j++)sid[i-1][j][i][j]=rd();
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m+1;j++)sid[i][j-1][i][j]=rd();
- while(l-r<=eps)
- {
- double mid=(l+r)*0.5;
- if(ck(mid))ans=mid,l=mid+eps;
- else r=mid-eps;
- }
- printf("%.3lf\n",ans);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2784277.html