生活随笔
收集整理的這篇文章主要介紹了
BZOJ3996 [TJOI2015]线性代数 【最小割】
小編覺得挺不錯(cuò)的,現(xiàn)在分享給大家,幫大家做個(gè)參考.
題目 給出一個(gè)NN的矩陣B和一個(gè)1N的矩陣C。求出一個(gè)1*N的01矩陣A.使得
D=（AB-C）A^T最大。其中A^T為A的轉(zhuǎn)置。輸出D
輸入格式 第一行輸入一個(gè)整數(shù)N，接下來N行輸入B矩陣，第i行第J個(gè)數(shù)字代表Bij.
輸出格式 輸出最大的D
輸入樣例 3
1 2 1
3 1 0
1 2 3
2 3 7
輸出樣例 2
提示 1<=N<=500
題解 我們將式子化簡，就是：\(\sum_{i = 1}^{n} \sum_{j = 1}^{n} Bij * Ai * Aj - \sum_{i}^{n} Ci * Ai\)
用最小割解決
我們假設(shè)一開始擁有所有價(jià)值
#include<iostream>
#include<cstdio>
#include<cmath>
#include<queue>
#include<cstring>
#include<algorithm>
#define LL long long int
#define Redge(u) for (int k = h[u],to; k; k = ed[k].nxt)
#define REP(i,n) for (int i = 1; i <= (n); i++)
#define BUG(s,n) for (int i = 1; i <= (n); i++) cout<<s[i]<<' '; puts("");
using namespace std;
const int maxn = 300005,maxm = 5000005,INF = 1000000000;
inline int read(){int out = 0,flag = 1; char c = getchar();while (c < 48 || c > 57){if (c == '-') flag = -1; c = getchar();}while (c >= 48 && c <= 57){out = (out << 3) + (out << 1) + c - 48; c = getchar();}return out * flag;
}
int h[maxn],ne = 2,n,m;
struct EDGE{int to,nxt,f;}ed[maxm];
inline void build(int u,int v,int w){ed[ne] = (EDGE){v,h[u],w}; h[u] = ne++;ed[ne] = (EDGE){u,h[v],0}; h[v] = ne++;
}
int d[maxn],vis[maxn],S,T,cur[maxn];
bool bfs(){for (int i = S; i <= T; i++) vis[i] = 0,d[i] = INF;queue<int> q;q.push(S); vis[S] = true; d[S] = 0;int u;while (!q.empty()){u = q.front(); q.pop();Redge(u) if (ed[k].f && !vis[to = ed[k].to]){d[to] = d[u] + 1; vis[to] = true;q.push(to);}}return vis[T];
}
int dfs(int u,int minf){if (u == T || !minf) return minf;int f,flow = 0,to;if (cur[u] == -1) cur[u] = h[u];for (int& k = cur[u]; k; k = ed[k].nxt)if (d[to = ed[k].to] == d[u] + 1 && (f = dfs(to,min(minf,ed[k].f)))){ed[k].f -= f; ed[k ^ 1].f += f;flow += f; minf -= f;if (!minf) break;}return flow;
}
int maxflow(){int flow = 0;while (bfs()){memset(cur,-1,sizeof(cur));flow += dfs(S,INF);}return flow;
}
int main(){n = read(); S = 0; T = n + n * n + 1;int x,ans = 0,id = n;for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){ans += (x = read()); id++;build(i,id,INF);build(j,id,INF);build(id,T,x);}}for (int i = 1; i <= n; i++) build(S,i,read());printf("%d\n",ans - maxflow());return 0;
}
轉(zhuǎn)載于:https://www.cnblogs.com/Mychael/p/8533427.html
《新程序員》：云原生和全面數(shù)字化實(shí)踐 50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀
總結(jié)
以上是生活随笔 為你收集整理的BZOJ3996 [TJOI2015]线性代数 【最小割】 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔 推薦給好友。
