传送门
Description
给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得
D=（A*B-C）*A^T最大。其中A^T为A的转置。输出D
Input
第一行输入一个整数N，接下来N行输入B矩阵，第i行第J个数字代表Bij.
接下来一行输入N个整数，代表矩阵C。矩阵B和矩阵C中每个数字都是不超过1000的非负整数。
Output
输出最大的D
这玩意……好像可以直接最大闭合权图？？？
25w个点有点慌啊。
可是不会其他做法了啊……
看看题解？怎么还真是直接流啊……
#include<set> #include<cstdio> #include<algorithm> #define MN 3100000 using namespace std; const int INF=1e9; struct na{int y,f,ne;}b[MN<<1]; int n,S,T,no,a,l[MN],num=1,mmh=0,d[MN],g[MN],c[MN]; inline void in(int x,int y,int f){b[++num].y=y;b[num].f=f;b[num].ne=l[x];l[x]=num;} inline void add(int x,int y,int f){in(x,y,f);in(y,x,f);} int sap(int x,int f){ if (x==T) return f; int h=0,q; for (int i=d[x];i;i=b[i].ne) if (g[b[i].y]+1==g[x]&&b[i].f){ q=sap(b[i].y,min(f-h,b[i].f));d[x]=i; h+=q;b[i].f-=q;b[i^1].f+=q; if (g[S]==no||h==f) return h; } if (!(--c[g[x]])) g[S]=no;c[++g[x]]++;d[x]=l[x]; return h; } int main(){ scanf("%d",&n);S=0;T=no=n*n+n+1; for (int i=0;i<n;i++) for (int j=0;j<n;j++) scanf("%d",&a),add(S,i*n+j+1,a),add(i*n+j+1,n*n+i+1,INF),add(i*n+j+1,n*n+j+1,INF),mmh+=a; for (int i=0;i<n;i++) scanf("%d",&a),add(n*n+i+1,T,a); for (;g[S]<no;mmh-=sap(S,INF)); printf("%d ",mmh); }