做网站单网页,九江濂溪区,网站建设费用推荐网络,北京市建设工程交易服务中心网站正题
luogu 1791 题目大意
有n个人#xff0c;选择第i个人的代价是aia_iai#xff0c;如果i,j同时被选那么有贡献wi,jw_{i,j}wi,j#xff0c;如果i选了j没选那么有贡献−wi,j-w_{i,j}−wi,j#xff0c;问你最大贡献#xff08;减去代价#xff09; 解题思路
最大…正题
luogu 1791 题目大意
有n个人选择第i个人的代价是aia_iai如果i,j同时被选那么有贡献wi,jw_{i,j}wi,j如果i选了j没选那么有贡献−wi,j-w_{i,j}−wi,j问你最大贡献减去代价 解题思路
最大权闭合子图模型考虑网络流
对于第i个点向s连一条流量为aia_iai的边向t连一条∑j1nwi,j\sum_{j1}^nw_{i,j}∑j1nwi,j的边假设所有点都选
那么考虑选的点与不选的点之间的连边如果两个点都选那么有利润wi,jw_{i,j}wi,j一个点不选利润为−wi,j-w_{i,j}−wi,j利润差为2wi,jw_{i,j}wi,j所以两个点之间连边的流量为2wi,jw_{i,j}wi,j
最后用总贡献减去最小割就是答案 代码
#includequeue
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
#define N 1010
using namespace std;
int n, s, t, x, y, tot, ans, dep[N], head[N];
const int inf 1000000000;
queueintd;
struct rec
{int to, next, f;
}e[N*NN*2];
void add(int x, int y, int z)
{e[tot].to y;e[tot].f z;e[tot].next head[x];head[x] tot;e[tot].to x;e[tot].f 0;e[tot].next head[y];head[y] tot;return;
}
bool bfs()
{memset(dep, 0, sizeof(dep));while (!d.empty()) d.pop();dep[s] 1;d.push(s);while(!d.empty()){int h d.front();d.pop();for (int i head[h]; i; i e[i].next)if (!dep[e[i].to] e[i].f){dep[e[i].to] dep[h] 1;if (e[i].to t) return true;d.push(e[i].to);}}return false;
}
int dfs(int x, int flow)
{if (x t) return flow;int rest 0, k;for (int i head[x]; i; i e[i].next)if (dep[e[i].to] dep[x] 1 e[i].f){k dfs(e[i].to, min(e[i].f, flow - rest));if (!k) dep[e[i].to] 0;rest k;e[i].f - k;e[i^1].f k;if (rest flow) return rest;}return rest;
}
int main()
{scanf(%d, n);s n 1;t n 2;tot 1;for (int i 1; i n; i){scanf(%d, x);add(s, i, x);}for (int i 1; i n; i){y 0;for (int j 1; j n; j){scanf(%d, x);if (x) add(i, j, 2 * x);ans x;y x;}add(i, t, y);}while(bfs())ans - dfs(s, inf);printf(%d, ans);return 0;
}
