[BZOJ 1449][JSOI2009]球队收益
二次函数费用流的入门题……我真太弱了……
可以给比赛、队伍都建点，然后\(S\)向每个比赛连容量为1的边，每个比赛向队伍连容量为\(1\)的边，来表示赢家是谁。这样一来一次比赛只有一个队伍赢了。
考虑怎么处理那个二次函数费用。费用函数为\(f(x, y) = C x^2 + D y^2\)，由于一个队伍的总比赛次数是已知的，所以\(y\)不需要，不妨假设一个队伍有\(t\)场比赛，则费用函数为\(f(x) = C x^2 + D(t - x)^2\)。
对这个函数做差分：\(\Delta f(x) = f(x + 1) - f(x) = 2Cx - 2D(t - x) + C + D\)，然后这个差分是单调不降的。因此我们对所有差分都从队伍向\(T\)连边（费用为这一点的差分），这样一来的话会优先选择费用小的边，保证这个队伍的费用一直合法。
代码：
/**************************************************************
Problem: 1449
User: danihao123
Language: C++
Result: Accepted
Time:732 ms
Memory:1448 kb
****************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
#include <cassert>
typedef long long ll;
const int maxn = 5005;
const int maxm = 1005;
const int maxno = maxn + maxm + 5;
const int maxe = (1000 * 2 + 1000 * 3) * 2 + 50;
int first[maxno];
int next[maxe], from[maxe], to[maxe], flow[maxe], cap[maxe];
ll cost[maxe];
int gcnt = 0;
void add_edge(int u, int v, int f, ll c) {
gcnt ++;
next[gcnt] = first[u];
first[u] = gcnt;
from[gcnt] = u; to[gcnt] = v;
cap[gcnt] = f; flow[gcnt] = 0;
cost[gcnt] = c;
}
int rev(int i) {
return ((i - 1) ^ 1) + 1;
}
void ins_edge(int u, int v, int f, ll c) {
add_edge(u, v, f, c);
add_edge(v, u, 0, -c);
}
int n, m;
const ll LINF = 0x7f7f7f7f7f7f7f7fLL;
bool spfa(int s, int t, int &f, ll &c) {
static ll d[maxno];
static bool inq[maxno];
static int a[maxno], p[maxno];
std::fill(d, d + n + m + 2, LINF);
std::fill(inq, inq + n + m + 2, false);
std::fill(a, a + n + m + 2, 0);
std::fill(p, p + n + m + 2, 0);
d[s] = 0;
std::queue<int> Q; Q.push(s); inq[s] = true;
a[s] = 0x7fffffff;
while(!Q.empty()) {
int u = Q.front(); Q.pop();
inq[u] = false;
for(int i = first[u]; i; i = next[i]) {
if(cap[i] > flow[i]) {
int v = to[i];
if(d[v] > d[u] + cost[i]) {
d[v] = d[u] + cost[i];
a[v] = std::min(a[u], cap[i] - flow[i]); p[v] = i;
if(!inq[v]) {
Q.push(v); inq[v] = true;
}
}
}
}
}
if(a[t] == 0) return false;
f += a[t];
c += (ll(a[t])) * d[t];
for(int e = p[t]; e; e = p[from[e]]) {
flow[e] += a[t];
flow[rev(e)] -= a[t];
}
return true;
}
void mcmf(int s, int t, int &f, ll &c) {
while(spfa(s, t, f, c));
}
ll win[maxn], lose[maxn], C[maxn], D[maxn];
ll tot[maxn];
int main() {
scanf("%d%d", &n, &m);
ll ans = 0;
for(int i = 1; i <= n; i ++) {
scanf("%lld%lld%lld%lld", &win[i], &lose[i], &C[i], &D[i]);
tot[i] = win[i] + lose[i];
}
int s = 0, t = n + m + 1;
for(int i = 1; i <= m; i ++) {
int a, b; scanf("%d%d", &a, &b);
ins_edge(0, i + n, 1, 0);
ins_edge(i + n, a, 1, 0);
ins_edge(i + n, b, 1, 0);
tot[a] ++; tot[b] ++;
}
for(int i = 1; i <= n; i ++) {
ans += C[i] * win[i] * win[i] + D[i] * (tot[i] - win[i]) * (tot[i] - win[i]);
for(ll j = win[i]; j <= (tot[i] - lose[i] - 1LL); j ++) {
ins_edge(i, t, 1, 2LL * C[i] * j - 2LL * D[i] * (tot[i] - j) + C[i] + D[i]);
}
}
int f = 0; mcmf(s, t, f, ans);
printf("%lld\n", ans);
return 0;
}
[BZOJ 1013]球型空间产生器
不行不能颓了……线代其实刚起步……
注意每个点到球心的距离相同，距离之平方亦相同。然后假设所有半径平方为[tex]d[/tex]，那么我们先可以列出两个方程（假设[tex]n=2[/tex]，不过此时事实上可以列三个，但出于方便讨论的目的便只列两个）：
[tex](x_1-a_1)^2+(x_2-a_2)^2=d[/tex]
[tex](x_1-b_1)^2+(x_2-b_2)^2=d[/tex]
两方程作差，得：
[tex](x_1-a_1)^2+(x_2-a_2)^2-(x_1-b_1)^2-(x_2-b_2)^2=0[/tex]
整理，得：
[tex]2(b_1-a_1)x_1+2(b_2-a_2)x_2=(b_1+a_1)(b_1-a_1)+(b_2+a_2)(b_2-a_2)[/tex]
对这种方法加以推广，便可列出[tex]n[/tex]个[tex]n[/tex]元一次方程。高斯消元求解即可。
代码：
/**************************************************************
Problem: 1013
User: danihao123
Language: C++
Result: Accepted
Time:4 ms
Memory:1296 kb
****************************************************************/
#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn=20;
int n;
double M[maxn][maxn];
double A[maxn][maxn];
inline void Gause(){
register int i,j,k,r;
register double f;
for(i=1;i<=n;i++){
r=i;
for(j=i+1;j<=n;j++)
if(fabs(A[j][i])>fabs(A[r][i]))
r=j;
if(r!=i)
for(j=1;j<=(n+1);j++)
swap(A[r][j],A[i][j]);
for(k=i+1;k<=n;k++){
f=A[k][i]/A[i][i];
for(j=i;j<=n+1;j++)
A[k][j]-=f*A[i][j];
}
}
for(i=n;i>=1;i--){
for(j=i+1;j<=n;j++)
A[i][n+1]-=A[j][n+1]*A[i][j];
A[i][n+1]/=A[i][i];
}
}
int main(){
register int i,j;
bool flag=false;
cin>>n;
for(i=1;i<=(n+1);i++)
for(j=1;j<=n;j++)
cin>>M[i][j];
for(i=1;i<=n;i++)
for(j=1;j<=(n+1);j++)
A[i][j]=0;
for(i=1;i<=n;i++){
for(j=1;j<=n;j++){
A[i][j]=2*(M[i+1][j]-M[i][j]);
A[i][n+1]+=(M[i+1][j]-M[i][j])*(M[i+1][j]+M[i][j]);
}
}
Gause();
for(i=1;i<=n;i++){
if(flag)
putchar(' ');
flag=true;
printf("%.3f",A[i][n+1]);
}
putchar('\n');
return 0;
}
[BZOJ 1029]建筑抢修
废了。
我彻底废了。
就一个贪心水体。按截止时间排序然后遍历，当前花时间能干完就干，不能的话看能不能把更劣的选择换。仅此而已。
代码：
/**************************************************************
Problem: 1029
User: danihao123
Language: C++
Result: Accepted
Time:396 ms
Memory:2764 kb
****************************************************************/
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;
#define REP(i,n) for(i=0;i<(n);i++)
#define REP_B(i,n) for(i=1;i<=(n);i++)
const int maxn=150001;
struct Node{
int a,b;
bool operator <(const Node& x) const{
return b<x.b;
}
bool operator >(const Node& x) const{
return b>x.b;
}
};
Node T[maxn];
priority_queue<ll> Q;
int main(){
int n;
register int i,ans=0;
register ll cur=0;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d%d",&T[i].a,&T[i].b);
sort(T+1,T+1+n);
for(i=1;i<=n;i++){
if(cur+T[i].a<=T[i].b){
cur+=T[i].a;
Q.push(T[i].a);
}else{
if(Q.size() && Q.top()>T[i].a){
cur-=Q.top();
Q.pop();
cur+=T[i].a;
Q.push(T[i].a);
}
}
}
printf("%d\n",Q.size());
return 0;
}
[BZOJ 1015]星球大战
这道题到现在才A……
其实……离线处理并不像我想的那样变态……
需要注意的是，离线处理过程中，在将被删除的点加入时，联通分量数可能增加（其他一个点都连不了）
代码：
