缩点+背包
1、如果第一个人确定选择一个点，那么跟第一点有关系（有冲突）的所有的点都可以确定是第一个人还是第二个人的。
2、所以可以将每个联通块缩成一个点，这个点用两个值
（在这里记录一下最小获得的 val
3、假设第一个人取了某个点最大的
4、但是我们想让两个人的差值尽量小，所以我们对第一个人能得到的“净val”做一下01背包，就得到了第一个人可能得到的“净val”。
5、两个人差值尽量小，我们就希望第一个人得到的“净val”接近总的“净val”的一半，所以，我们可以从总的“净val”的一半开始往后找，如果找到了第一个人可以得到的“净val”的话，就相当于找到了使两个人差值最小的选择方法，然后答案就等于最大的“净val”加上上面求的最小获得的val。
#include <bits/stdc++.h>
#define Pair pair<int,int>
using namespace std;
int dp[505 * 505];
const int MAXN = 205;
vector<int>v[205];
int a[MAXN];
bool vis[205];
void dfs(int u, int& sum1, int& sum2, int bas)
{
for (int i = 0; i < v[u].size(); i++)
{
int to = v[u][i];
if (vis[to] == true)
continue;
vis[to] = true;
if (bas > 0)
sum1 += a[to];
else
sum2 += a[to];
dfs(to, sum1, sum2, bas * -1);
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
int SUM = 0;
vector<Pair>ans;
memset(vis, false, sizeof(vis));
memset(dp, 0, sizeof(dp));
int n, m;
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
a[i] /= 100;
SUM += a[i];
v[i].clear();
}
while (m--)
{
int q, w;
scanf("%d%d", &q, &w);
v[q].push_back(w);
v[w].push_back(q);
}
int sum = 0;
for (int i = 1; i <= n; i++)
{
if (vis[i] == false)
{
int sol1 = a[i];
int sol2 = 0;
vis[i] = true;
dfs(i, sol1, sol2, -1);
ans.push_back(Pair(sol1, sol2));
sum += min(sol1, sol2);
}
}
dp[0] = 1;
int cha = 0;
for (int i = 0; i < ans.size(); i++)
{
int temp = abs(ans[i].first - ans[i].second);
cha += temp;
for (int j = SUM; j >= temp; j--)
{
if (dp[j - temp])
dp[j] = 1;
}
}
for (int i = cha / 2; i <= cha; i++)
{
if (dp[i])
{
printf("%d\n", (max(i, cha - i) + sum) * 100);
break;
}
}
}
} 几何，求切点（上板子
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <vector>
#include <algorithm>
const double eps = 1e-6;
const double PI = acos(-1.0); // PI = 180°= 3.14
using namespace std;
//判断符号
int sign(double x)
{
if (fabs(x) < eps)
return 0;
return x > 0 ? 1 : -1;
}
struct point
{
double x;
double y;
point operator + (const point& other) { return point{ x + other.x, y + other.y }; }
point operator - (const point& other) { return point{ x - other.x, y - other.y }; }
point operator * (double k) { return point{ x * k, y * k }; }
point operator / (double k) { return point{ x / k, y / k }; }
bool operator == (const point& other)
{
return sign(x - other.x) == 0 && sign(y - other.y) == 0;
}
bool operator < (const point & other)
{
if (fabs(x - other.x) < eps)
return y < other.y;
return x < other.x;
}
};
//点积
double dot(point a, point b)
{
return a.x* b.x + a.y * b.y;
}
//叉积
double cross(point a, point b)
{
return a.x* b.y - b.x * a.y;
}
//向量的长度 (可以计算两点距离
double getlen(point a)
{
return sqrt(a.x * a.x + a.y * a.y);
}
//两向量夹角
double getangle(point a, point b)
{
return acos(dot(a, b) / getlen(a) / getlen(b));
}
//点P 绕 点O 逆时针旋转angle角度(弧度制)
point rotate(point p, point o, double angle)
{
point t = point{ p.x - o.x,p.y - o.y };
double c = cos(angle), s = sin(angle);
return point{ o.x + t.x * c - t.y * s,o.y + t.x * s + t.y * c };
}
struct circle
{
point o;
double r;
};
//经过点p，作圆o的切线，sol是切点数组，返回值为切点数
int gettangents(point p, circle oo, vector<point> & sol)
{
double dis = getlen(p - oo.o);
if (dis < oo.r)
return 0;
else if (sign(dis - oo.r) == 0)
{
sol.push_back(rotate(oo.o, p, PI / 2));
return 1;
}
else
{
double angle = asin(oo.r / dis);
sol.push_back(rotate(oo.o, p, angle));
sol.push_back(rotate(oo.o, p, -angle));
return 2;
}
}
int main()
{
int T;
scanf("%d", &T);
while (T--)
{
point a; circle o;
scanf("%lf%lf%lf%lf%lf", &o.o.x, &o.o.y, &o.r, &a.x, &a.y);
point l = point{ o.o.x - o.r,o.o.y }, r = point{ o.o.x + o.r,o.o.y };
point b = point{ o.o.x,o.o.y - o.r };
vector<point>sol;
int cnt = gettangents(a, o, sol);
double ans = 99999999;
for (int i = 0; i < cnt; i++)
{
double dis = getlen(a - sol[i]);
sol[i] = (sol[i] - a) * (sqrt(dis * dis - o.r * o.r)) / dis + a;
if (sign(sol[i].y - o.o.y) < 0)
{
if (sign(sol[i].x - o.o.x) < 0)
sol[i] = l;
else
sol[i] = r;
}
double res = getlen(a - sol[i]) + getangle(sol[i] - o.o, b - o.o) * o.r;
ans = min(ans, res);
}
printf("%.4lf\n", ans);
}
}
京公网安备 11010502036488号