https://odzkskevi.qnssl.com/7dfb262544887eff6fb35bfb444759d6?v=1502084197
做法是类似于最大割之类的东西，把每个碎片按照按钮拆点，从s到每个碎片第一个点连inf，每个碎片第i个按钮向第i+1个按钮连100-i能量。
然后最大流最小割，最大流=割掉的边和=100*n-能量和的最大值。
#include<cstring> #include<algorithm> #include<cmath> #include<cstdio> #define rep(i,l,r) for(int i=l;i<=r;i++) #define dow(i,l,r) for(int i=r;i>=l;i--) #define rep0(i,r) for(int i=0;i<r;i++) #define repedge(i,x) for(int i=cur[x];i>=0;i=e[i].next) #define maxn 20020 #define maxm 200100 #define LL long long using namespace std; typedef struct { int next,f,t; }E; E e[maxm]; int gap[maxn],d[maxn],fi[maxn],cur[maxn],s,t,total=0; const int inf=100000000; int n,m,q; void add(int j,int k,int l) { e[total].f=l; e[total].t=k; e[total].next=fi[j]; fi[j]=total; total++; } void addedge(int j,int k,int l) { add(j,k,l); add(k,j,0); } int sap(int x,int flow) { if (x==t) return flow; int now=0; repedge(i,x) { int too=e[i].t; if (d[too]+1==d[x] && e[i].f) { int more=sap(too,min(e[i].f,flow-now)); e[i].f-=more; e[i^1].f+=more; cur[x]=i; if (flow==(now+=more)) return flow; } } if (!(--gap[d[x]])) d[s]=t; gap[++d[x]]++; cur[x]=fi[x]; return now; } int maxflow() { memset(d,0,sizeof(d)); memset(gap,0,sizeof(gap)); rep(i,1,t) cur[i]=fi[i]; gap[0]=t; int ans=0; while (d[s]<t) ans+=sap(s,inf); //printf("%d ",ans); return ans; } int main() { // freopen("1.in","r",stdin); scanf("%d %d",&n,&m); memset(fi,-1,sizeof(fi)); s=n*(m+1)+1; t=s+1; rep(i,1,n) { int now=(i-1)*(m+1); addedge(s,now+1,inf); addedge(now+m+1,t,inf); rep(j,1,m) { int k; scanf("%d",&k); if (k!=-1) addedge(now+j,now+j+1,100-k); else addedge(now+j,now+j+1,inf); } } scanf("%d",&q); while (q--) { int j,k; scanf("%d %d",&j,&k); rep(i,1,m) { int now1=(j-1)*(m+1)+i; int now2=(k-1)*(m+1)+i+1; addedge(now1,now2,inf); } } //printf("%d ",maxflow()); printf("%.2lf ",(100.0*n-maxflow())/(n+0.0)); return 0; }
- 我1