HDU 6445(竞赛图 + 网络流)

60 阅读 0 评论 40 点赞

我是靠谱客的博主坚强美女，最近开发中收集的这篇文章主要介绍HDU 6445(竞赛图 + 网络流)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：给出一个n(<=200)个节点的竞赛图，计算图中所给的ans.

枚举四元组(a, b, c, d) ,
四元组一共有3种情况:
1. 成环 ans ++, 也就是有向环组成的。
2. 不成环， ans不变，也就是说有且仅有一个点的出度为2
3. 不成换，ans– , 拥有两个点出度为2.

一共有A(n, 4)种组合，枚举每一个度数>=2的点，对于其出度的点，有C（deg, 2）种选法，剩下一个点在(n - 3)种选择。
最后要求的就是 A(n,4)−∑A(deg,2)∗(n−3)∗4 A ( n , 4 ) − ∑ A ( d e g , 2 ) ∗ ( n − 3 ) ∗ 4

实际上要找的就是 ∑C(deg,2) ∑ C ( d e g , 2 )

我们考虑用费用流来计算上式的最小值。

建立两列点，左边一列代表方向不确定的边，右边代表1-n节点，左边会拉出两条边连向右边的点，源连左边，右边连汇，如果我们求的是 ∑deg ∑ d e g ，这道题就已经结束了。

现在改成 C(deg,2) C ( d e g , 2 ) , 我们一定做过边权和n^2 有关的那道题(没有请自己翻紫书)，这题如是。

贴简要代码:

#include <bits/stdc++.h>
const int N = 1e3+9;
using namespace std;
using ll = long long;
int n, deg[N], ecnt[N];
char s[202][202];
namespace MCMF { ... }
void init() { memset(ecnt, 0, sizeof ecnt); memset(deg, 0, sizeof deg); MCMF::init(); }
int main() {
int t; scanf("%d", &t);
while(t--) {
init(); scanf("%d", &n); int tot = n+1; ll tmp = 0;
for (int i = 1; i <= n; i++) {
scanf("%s", s[i]+1);
for (int j = 1; j <= n; j++) {
if(s[i][j] == '1') deg[i]++;
else if(s[i][j] == '2' && i < j) {
ecnt[i] ++; ecnt[j] ++;
MCMF::add(tot, i, 1, 0); MCMF::add(tot, j, 1, 0); tot++;
}
}
}
MCMF::s = n+tot, MCMF::t = n+tot+1;
for (int i = n+1; i < tot; i++) MCMF::add(MCMF::s, i, 1, 0);
for (int i = 1; i <= n; i++) {
int tt = deg[i];
tmp += tt*(tt-1)/2;
for (int j = 0; j < ecnt[i]; j++) MCMF::add(i, MCMF::t, 1, tt++);
}
MCMF::MCMF(); tmp += MCMF::ans;
tmp = n*(n-1)*(n-2)*(n-3) - tmp * (n - 3) * 8;
printf("%lldn", tmp);
}
return 0;
}