题意：给出一个NN的矩阵B和一个1N的矩阵C。求出一个1*N的01矩阵A.使得
\(D=（A * B-C）* A^T\)最大。其中A^T为A的转置。输出D。每个数非负。
分析一下这个乘法的性质或者化简一下容易发现，\(C_i\)代价生效需要\(A_i=1\)，\(B_{ij}\)贡献生效需要\(A_i =A_j=1\)
最小割
我成功的把dinic里的括号打错了...gg
#include#include #include #include using namespace std;typedef long long ll;const int N=300005, M=2e6+5, INF = 1e9;inline int read() { char c=getchar(); int x=0,f=1; while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();} while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();} return x*f;}int n, b[505][505], c[505], sum;struct edge{int v, ne, c, f;} e[M];int cnt=1, h[N], s, t;inline void ins(int u, int v, int c) { e[++cnt] = (edge){v, h[u], c, 0}; h[u] = cnt; e[++cnt] = (edge){u, h[v], 0, 0}; h[v] = cnt;}namespace mf { int q[N], head, tail, vis[N], d[N]; bool bfs() { memset(vis, 0, sizeof(vis)); head = tail = 1; q[tail++] = s; d[s] = 0; vis[s] = 1; while(head != tail) { int u = q[head++]; for(int i=h[u];i;i=e[i].ne) if(!vis[e[i].v] && e[i].c > e[i].f) { int v = e[i].v; vis[v] = 1; d[v] = d[u]+1; q[tail++] = v; if(v == t) return true; } } return false; } int cur[N]; int dfs(int u, int a) { if(u == t || a == 0) return a; int flow = 0, f; for(int &i=cur[u];i;i=e[i].ne) if(d[e[i].v] == d[u]+1 && (f = dfs(e[i].v, min(a, e[i].c - e[i].f)) ) >0 ) { flow += f; e[i].f += f; e[i^1].f -= f; a -= f; if(a == 0) break; } if(a) d[u] = -1; return flow; } int dinic() { int flow = 0; while(bfs()) { for(int i=s; i<=t; i++) cur[i] = h[i]; flow += dfs(s, INF); } return flow; }}void build() { s = 0; t = n + n*n + 1; for(int i=1; i<=n; i++) ins(s, i, c[i]), ins(i, t, b[i][i]); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) if(i != j) { int id = i*n+j; ins(i, id, INF); ins(j, id, INF); ins(id, t, b[i][j]); }}int main() { freopen("in", "r", stdin); n = read(); for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) b[i][j] = read(), sum += b[i][j]; for(int i=1; i<=n; i++) c[i] = read(); build(); int ans = mf::dinic(); printf("%d\n", sum - ans);}