[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……
其实……离线处理并不像我想的那样变态……
需要注意的是,离线处理过程中,在将被删除的点加入时,联通分量数可能增加(其他一个点都连不了)
代码: