1449: [JSOI2009]球队收益
Time Limit: 5 Sec Memory Limit: 64 MBSubmit: 648 Solved: 364[][][]Description
Input
Output
Sample Input
Sample Output
HINT
Source
2895: 球队预算
Time Limit: 10 Sec Memory Limit: 256 MBSubmit: 51 Solved: 50[][][]Description
Input
Output
Sample Input
Sample Output
HINT
Source
Solution
idea很好的建图,不能考虑直接建,而应该利用增量的思想
个人的想法是这样的:
源到各比赛连边,容量为1,费用为0
建每个球队分成两个,由个比赛连向两只球队a,b,再由a连b',b连a',分别表示a赢了这场比赛或b赢了这场比赛
然后由各个点i'连向汇容量为inf,费用为0
然后预处理出来已比完的比赛胜负的价值,加上最小费用即可;
思路是考虑一场比赛的胜负对于结果的贡献,从这场比赛结束后对结果的增量来考虑,但显然这种方法并不是很优,但理论上可A
那么同样的思想,换一种方法建图:
不妨先假设后面的M场比赛中双方都是输家,这样我们只要在模型中表示一方成为赢家即可。
此应该有一个初步的模型了:对于N支球队和M场比赛各建一个点,从源向每场比赛连流量1费用0的边,从比赛向参与这场比赛的两支队伍各连一条流量1费用0的边。剩下的就是队伍收益的费用表示了。
多赢一场比赛产生的收益。即(C*(w+1)^2+D*(l-1)^2)-(C*w^2+D*l^2)=2w*C-2l*D+C+D。对于第i支队伍,假设后M场中i参加的有x场,那么最初w=win,l=lose+x,之后每赢一场w++,l--。我们从第i支队伍的点向汇连x条边,分别代表第i支队伍赢了j场比赛时相对赢j-1场时收益的增量。由于增量一定越来越大(平方嘛),所以流量最先流过的一定是费用较小的边,即j最小的边。
-----by huzecong
Code
#include#include #include #include #include #include using namespace std;int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0' || ch>'9') { if (ch=='-')f=-1; ch=getchar();} while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f;}#define maxn 5100+1100#define maxm 100100int n,m,ans,S,T,num[5010];struct Teamnode{ int win,lose,C,D;}team[5010];struct Edgenode{ int to,next,cap,cost,from;}edge[maxm];int head[maxn],cnt=1;void add(int u,int v,int w,int c) {cnt++;edge[cnt].from=u;edge[cnt].to=v; edge[cnt].next=head[u];head[u]=cnt; edge[cnt].cost=c;edge[cnt].cap=w;} void insert(int u,int v,int w,int c){add(u,v,w,c);add(v,u,0,-c);} #define inf 0x7fffffffint q[maxn],h,t; int dis[maxn];bool mark[maxn];bool spfa(){ memset(mark,0,sizeof(mark)); for (int i=S; i<=T; i++) dis[i]=inf; h=0,t=1; q[0]=T; mark[T]=1; dis[T]=0; while (h
吐槽一句..增广的过程中,一开始使用STL中的queue然后莫名的WA了?手写了个q...怒A...跑得飞快