CONTENT: Practice - 2019.05.14
DETAIL: 全局最小割、树的最小表示、线段相交、2-SAT
Introduction
本次Practice主要是涉及一些之前没有涉及过的数据结构与算法
- 全局最小割
https://github.com/lostRating/ACM_Templates/blob/master/%E5%9B%BE%E8%AE%BA/%E5%85%A8%E5%B1%80%E6%9C%80%E5%B0%8F%E5%89%B2.cpp
https://www.cnblogs.com/oyking/p/7339153.html - 树的最小表示
https://wenjing233.github.io/2019/03/21/zi-fu-chuan-de-zui-xiao-biao-shi-fa-shu-de-zui-xiao-biao-shi-fa-xue-xi-bi-ji/
Nubulsa Expo - HDU 3691
Link
https://cn.vjudge.net/problem/HDU-3691
Description
给定图，源点s，求min{maxflow(s, t)}, t∈({1, 2, …, n} - {s})
Sample Input
5 5 1
1 2 5
2 4 6
1 3 7
3 4 3
5 1 10
0 0 0
Sample Output
8
Solution —— 全局最小割 Store Wagner算法
maxflow(s,t)等价于mincut(s,t)
设全局最小割把点集分为了U和V，若mincut(s,t)不是全局最小割，那么则说明s, t∈U或s, t∈V，那么必然可以找到一点t’使得s与t’不同时在U或V中，此时mincut(s, t’)是全局最小割
因此答案与s无关，只需要求全局最小割即可
（然而看不懂全局最小割 Store Wagner算法 QAQ）
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef long long ll;
const ll inf = 0x3f3f3f3f3f3f3f3fLL;
const int N = 300 + 5;
bool used[N];
int v[N];
ll dis[N], G[N][N];
ll storeWagner(int n) {
ll res = inf;
for(int i = 0; i < n; i++) {
v[i] = i;
}
while(n > 1) {
used[v[0]] = 1 ;
for(int i = 1; i < n; i++) {
used[v[i]] = 0 ;
dis[v[i]] = G[v[0]][v[i]];
}
int last = 0;
for(int i = 1; i < n; i++) {
int maxs = -1;
for(int j = 1; j < n; j++) {
if(used[v[j]] == false && (maxs == -1 || dis[v[j]] > dis[v[maxs]])) {
maxs = j;
}
}
used[v[maxs]] = 1;
if(i == n - 1) {
res = min(res, dis[v[maxs]]);
for(int j = 0 ; j < n; j++) {
G[v[last]][v[j]] += G[v[maxs]][v[j]];
G[v[j]][v[last]] += G[v[j]][v[maxs]];
}
v[maxs] = v[--n];
break;
}
last = maxs;
for(int j = 1; j < n; j++) {
if(used[v[j]] == false) {
dis[v[j]] += G[v[maxs]][v[j]];
}
}
}
}
return res;
}
int main() {
int n, m, s;
while(~scanf("%d%d%d", &n, &m, &s) && (n && m && s)) {
memset(G, 0, sizeof(G));
while(m--) {
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
G[u - 1][v - 1] += w;
G[v - 1][u - 1] += w;
}
printf("%lld\n", storeWagner(n));
}
}
Distinct Subtrees - HDU 4013
Link
https://cn.vjudge.net/problem/HDU-4013
Description
问给定的无根树中有多少不同的子树
Sample Input
2
3
1 2
1 3
9
9 4
4 3
1 3
7 4
1 6
5 7
2 4
6 8
Sample Output
Case #1: 3
Case #2: 21
Solution —— 树的最小表示
枚举节点，以此枚举出所有的子树
对每一棵子树，枚举根节点的位置跑树的最小表示
如果其中有一种在set中出现过，那么说明出现了相同的子树，不再枚举该子树的根
否则压入set中，答案+1
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 15 + 2;
struct edge {
int v, nxt;
};
edge e[N << 1];
int head[N], tot;
inline void init() {
memset(head, -1, sizeof(head));
tot = 0;
}
inline void addEdge(int u, int v) {
e[tot] = edge{v, head[u]};
head[u] = tot++;
}
int isConnected(int u, int pre, const int& selSt) {
int curSt = 1 << u;
for(int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if(v == pre || ((~selSt >> v) & 1)) {
continue;
}
curSt |= isConnected(v, u, selSt);
}
return curSt;
}
string dfs(int u, int pre, const int& selSt) {
string ret = "1";
vector<string> vec;
for(int i = head[u]; ~i; i = e[i].nxt) {
int v = e[i].v;
if(v == pre || ((~selSt >> v) & 1)) {
continue;
}
vec.emplace_back(dfs(v, u, selSt));
}
sort(vec.begin(), vec.end());
for(auto& ele : vec) {
ret += ele;
}
ret += "0";
return ret;
}
int solve(int n) {
unordered_set<string> strSt;
int ans = 0;
for(int st = 0; st < (1 << n); st++) {
int selSt = st << 1;
vector<int> srcVec;
for(int u = 1; u <= n; u++) {
if((selSt >> u) & 1) {
srcVec.emplace_back(u);
}
}
if(srcVec.empty() || isConnected(srcVec[0], -1, selSt) != selSt) {
continue;
}
vector<string> resVec;
for(auto ele : srcVec) {
resVec.emplace_back(dfs(ele, -1, selSt));
}
if(!strSt.count(resVec[0])) {
ans++;
for(auto& ele : resVec) {
strSt.emplace(ele);
}
}
}
return ans;
}
int main() {
int t, csn = 1;
scanf("%d", &t);
while(t--) {
init();
int n;
scanf("%d", &n);
for(int i = 1; i <= n - 1; i++) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
addEdge(v, u);
}
printf("Case #%d: %d\n", csn++, solve(n));
}
return 0;
}
Fermat Point in Quadrangle - HDU 3694
Link
https://cn.vjudge.net/problem/HDU-3694
Description
给定四个点，求一个点使得到四个点的距离和最小，求此距离和
Sample Input
0 0 1 1 1 0 0 1
1 1 1 1 1 1 1 1
-1 -1 -1 -1 -1 -1 -1 -1
Sample Output
2.8284
0.0000
Solution —— 线段相交
如果组成凸多边形，显然该点在对角线的交点上
如果组成凹多边形，那么该点在顶点上
判断是否组成凸多边形，即枚举所有对边判断是否有交点，如果存在就说明是凸多边形，否则是凹多边形
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 300 + 15;
const int M = 1000 + 15;
const double eps = 1e-6;
struct Point {
double x, y;
};
int dcmp(double d) {
return fabs(d) < eps ? 0 : ((d > 0) ? 1 : -1);
}
double sqr(double x) {
return x * x;
}
//求两个向量叉乘：AB * AC
double cross(const Point &A, const Point &B, const Point &C) {
return (B.x - A.x) * (C.y - A.y) - (B.y - A.y) * (C.x - A.x);
}
int xycmp(double p, double mini, double maxi) {
return dcmp(p - mini) * dcmp(p - maxi);
}
/*
前提条件：a在bc直线上
返回：
1表示a不在线段bc上
0表示a在b点或者c点上
-1表示a在线段bc上
*/
int betweencmp(const Point &a, const Point &b, const Point &c) {
if(fabs(b.x - c.x) > fabs(b.y - c.y)) return xycmp(a.x, min(b.x, c.x), max(b.x, c.x));
else return xycmp(a.y, min(b.y, c.y),max(b.y, c.y));
}
double getDis(const Point& a, const Point& b) {
return sqrt(sqr(a.x - b.x) + sqr(a.y - b.y));
}
//判断线段ab是否与cd相交， 交点记在p
//返回值：0表示不相交； 1表示规范相交； 2表示非规范相交
int segcross(const Point &a, const Point &b, const Point &c, const Point &d, Point &p) { //p用于引用返回数
double s1, s2, s3, s4;
int d1, d2, d3, d4;
d1 = dcmp(s1 = cross(a, b, c));
d2 = dcmp(s2 = cross(a, b, d));
d3 = dcmp(s3 = cross(c, d, a));
d4 = dcmp(s4 = cross(c, d, b));
//判断规范相交：交点不会在端点上
if((d1 ^ d2) == -2 && (d3 ^ d4) == -2) {
p.x = (c.x * s2 - d.x * s1) / (s2-s1);
p.y = (c.y * s2 - d.y * s1) / (s2-s1);
return 1;
}
// 判断非规范相交：交点在端点上
if(d1 == 0 && betweencmp(c, a, b) <= 0) {
p = c;
return 2;
}
if(d2 == 0 && betweencmp(d, a, b) <= 0) {
p = d;
return 2;
}
if(d3 == 0 && betweencmp(a, c, d) <= 0) {
p = a;
return 2;
}
if(d4 == 0 && betweencmp(b, c, d) <= 0) {
p = d;
return 2;
}
return 0;
}
int main() {
Point pt[5];
while(true) {
for(int i = 0; i < 4; i++) {
scanf("%lf%lf", &pt[i].x, &pt[i].y);
}
if(pt[0].x == -1) {
break;
}
bool isConvex = false;
if(!isConvex) {
isConvex = segcross(pt[0], pt[1], pt[2], pt[3], pt[4]);
}
if(!isConvex) {
isConvex = segcross(pt[0], pt[2], pt[1], pt[3], pt[4]);
}
if(!isConvex) {
isConvex = segcross(pt[0], pt[3], pt[1], pt[2], pt[4]);
}
double dis = 0;
if(isConvex) {
for(int i = 0; i < 4; i++) {
dis += getDis(pt[i], pt[4]);
}
} else {
double maxx = 1e18;
for(int i = 0; i < 4; i++) {
double tmp = 0;
for(int j = 0; j < 4; j++) {
if(i == j) {
continue;
}
tmp += getDis(pt[i], pt[j]);
}
maxx = min(maxx, tmp);
}
dis = maxx;
}
printf("%.4f\n", dis);
}
}
Go Deeper - UVALive 5010
Link
https://cn.vjudge.net/problem/UVALive-5010
Description
go(int dep, int n, int m)
begin
output the value of dep.
if dep < m and x[a[dep]] + x[b[dep]] != c[dep] then go(dep + 1, n, m)
end
{0, 1} in x, {0, 1, 2} in c, len(a) = len(b) = len(c) = m, len(x) = n
给定a,b,c，构造x，问dep的最大值
Sample Input
3
2 1
0 1 0
2 1
0 0 0
2 2
0 1 0
1 1 2
Sample Output
1
1
2
Solution —— 2-SAT + 二分
利用条件将语句等价于多个A is True/False or B is True/False语句，变形为2-SAT
再加上二分添加[0,k]个语句，k的最大值+1即是答案
#include <bits/stdc++.h>
using namespace std;
const int N = 200 + 15;
const int M = 1e6 + 15;
struct edge {
int v, nxt;
};
edge e[M];
int a[M], b[M], c[M];
int head[N * 2], tot;
bool mark[N * 2];
int stk[N * 2], pstk;
inline void init() {
memset(head, -1, sizeof(head));
memset(mark, false, sizeof(mark));
tot = pstk = 0;
}
inline void addEdge(int u, int v) {
e[tot] = edge{v, head[u]};
head[u] = tot++;
}
inline void addClause(int x, int xval, int y, int yval) {
x = x << 1 | xval;
y = y << 1 | yval;
addEdge(x^1, y);
addEdge(y^1, x);
}
bool dfs(int x) {
if(mark[x^1]) {
return false;
}
if(mark[x]) {
return true;
}
mark[x] = true;
stk[pstk++] = x;
for(int i = head[x]; ~i; i = e[i].nxt) {
int v = e[i].v;
if(!dfs(v)) {
return false;
}
}
return true;
}
bool solve() {
for(int i = 0; i < 2 * N; i += 2) {
if(!mark[i] && !mark[i + 1]) {
pstk = 0;
if(!dfs(i)) {
while(pstk > 0) {
mark[stk[--pstk]] = false;
}
if(!dfs(i + 1)) {
return false;
}
}
}
}
return true;
}
int main() {
int t;
scanf("%d", &t);
while(t--) {
int n, m;
scanf("%d%d", &n, &m);
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &a[i], &b[i], &c[i]);
}
int l = 0, r = m - 1, ans = -1;
while(l <= r) {
init();
int mid = (l + r) >> 1;
for(int i = 0; i <= mid; i++) {
int u = a[i] + 1;
int v = b[i] + 1;
if(c[i] == 0) {
addClause(u, 0, v, 0);
} else if(c[i] == 1) {
addClause(u, 1, v, 0);
addClause(u, 0, v, 1);
} else {
addClause(u, 1, v, 1);
}
}
if(solve()) {
ans = mid;
l = mid + 1;
} else {
r = mid - 1;
}
}
printf("%d\n", ans + 1);
}
}
