关键词：
Submit: 741 Solved: 423
Description
Input
Output
Sample Input
1 0 2 1
1 1 10 1
0 1 3 3
1 2
2 3
3 1
Sample Output
HINT
Source
最小费用最大流。
比赛无论胜负都会给球队带来收益，使得建边极为困难。考虑转化问题，首先假设每场比赛的结果是“两方都输”，以此为初始状态，之后决策某个队伍胜利，则获得的收益为“赢的收益-输的收益”。
1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #include<queue> 6 #include<cstring> 7 using namespace std; 8 const int INF=1e8; 9 const int mxn=9000; 10 int read(){ 11 int x=0,f=1;char ch=getchar(); 12 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} 13 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} 14 return x*f; 15 } 16 struct edge{ 17 int from,v,nxt; 18 int f,w; 19 }e[mxn<<1]; 20 int hd[mxn],mct=1;// 21 void add_edge(int u,int v,int c,int w){ 22 e[++mct].v=v;e[mct].from=u;e[mct].nxt=hd[u];e[mct].f=c;e[mct].w=w;hd[u]=mct;return; 23 } 24 // 25 int n,m; 26 int S,T; 27 int ans=0; 28 int win[mxn],lose[mxn],c[mxn],d[mxn]; 29 // 30 int dis[mxn]; 31 bool inq[mxn]; 32 int pre[mxn<<1]; 33 void SPFA(int s){ 34 memset(dis,0x3f,sizeof dis); 35 memset(pre,-1,sizeof pre); 36 queue<int>q; 37 dis[s]=0; 38 inq[s]=1; 39 q.push(s); 40 while(!q.empty()){ 41 int u=q.front();q.pop();inq[u]=0; 42 for(int i=hd[u];i;i=e[i].nxt){ 43 if(!e[i].f)continue; 44 int v=e[i].v; 45 if(dis[v]>dis[u]+e[i].w){ 46 dis[v]=dis[u]+e[i].w; 47 pre[v]=i;//记录前驱边 48 if(!inq[v]){ 49 inq[v]=1; 50 q.push(v); 51 } 52 } 53 } 54 } 55 return; 56 } 57 void maxflow(int s,int t){ 58 SPFA(s); 59 while(pre[t]!=-1){ 60 int tmp=INF; 61 for(int i=pre[t];i!=-1;i=pre[e[i].from]) 62 tmp=min(tmp,e[i].f); 63 ans+=dis[t]*tmp; 64 for(int i=pre[t];i!=-1;i=pre[e[i].from]){ 65 e[i].f-=tmp; 66 e[i^1].f+=tmp; 67 } 68 SPFA(s); 69 } 70 return; 71 } 72 int a[mxn],b[mxn]; 73 int main() 74 { 75 int i,j,u,v; 76 n=read();m=read(); 77 for(i=1;i<=n;i++){ 78 win[i]=read();lose[i]=read(); 79 c[i]=read();d[i]=read(); 80 } 81 for(i=1;i<=m;i++){ 82 a[i]=read();b[i]=read(); 83 ++lose[a[i]];++lose[b[i]]; 84 } 85 for(i=1;i<=n;i++){//假设全部都输掉 86 ans+=c[i]*win[i]*win[i]; 87 ans+=d[i]*lose[i]*lose[i]; 88 } 89 S=0;T=m+n+2; 90 for(i=1;i<=m;i++){ 91 add_edge(S,i,1,0); 92 add_edge(i,S,0,0); 93 add_edge(i,m+a[i],1,0); 94 add_edge(m+a[i],i,0,0); 95 add_edge(i,m+b[i],1,0); 96 add_edge(m+b[i],i,0,0); 97 //a 98 int cost=c[a[i]]*(2*win[a[i]]+1)-d[a[i]]*(2*lose[a[i]]-1); 99 add_edge(m+a[i],T,1,cost); 100 add_edge(T,m+a[i],0,-cost); 101 win[a[i]]++;lose[a[i]]--; 102 //b 103 cost=c[b[i]]*(2*win[b[i]]+1)-d[b[i]]*(2*lose[b[i]]-1); 104 add_edge(m+b[i],T,1,cost); 105 add_edge(T,m+b[i],0,-cost); 106 win[b[i]]++;lose[b[i]]--; 107 } 108 maxflow(S,T); 109 printf("%d ",ans); 110 return 0; 111 }
bzoj1449/2895[jsoi2009]球队收益/球队预算最小费用最大流
【BZOJ2895】球队预算Description在一个篮球联赛里，有n支球队，球队的支出是和他们的胜负场次有关系的，具体来说，第i支球队的赛季总支出是Ci*x^2+Di*y^2，Di<=Ci。(赢得多，给球员的奖金就多嘛)其中x,y分别表示这只球队本赛季的... 查看详情
网络流暂结（还差很多额）
...zoj1565:[NOI2009]植物大战僵尸最大权闭合子图bzoj1449:[JSOI2009]球队收益最小费用最大流（拆方）bzoj2502 查看详情
bzoj1449&&2895球队预算[费用流]
球队预算TimeLimit:10Sec MemoryLimit:256MB[Submit][Status][Discuss]Description 在一个篮球联赛里，有n支球队， 球队的支出是和他们的胜负场次有关系的，具体来说，第i支球队的赛季总支出是Ci*x^2+Di*y^2，Di<=Ci。(赢得多，给球... 查看详情
bzoj1443:[jsoi2009]游戏game
1443:[JSOI2009]游戏GameTimeLimit:10SecMemoryLimit:162MBSubmit:1334Solved:613[Submit][Status][Discuss]DescriptionInput输入数据首先输入两个整数N,M，表示了迷宫的边长。接下来N行，每行M个字符，描述了迷宫。Output若小AA能够赢得游戏，则输出一行"WIN... 查看详情
bzoj2257:[jsoi2009]瓶子和燃料
2257:[Jsoi2009]瓶子和燃料TimeLimit: 10Sec MemoryLimit: 128MBDescriptionjyy就一直想着尽快回地球，可惜他飞船的燃料不够了。 有一天他又去向火星人要燃料，这次火星人答应了，要jyy用飞船上的瓶子来换。jyy的飞船上共... 查看详情
bzoj1452:[jsoi2009]count
DescriptionInputOutputSampleInputSampleOutput12HINT 题目传送门 话说这好像是我第一次做树状数组的题树状数组裸题，还是二维的，多一层for而已 代码如下：#include<cmath>#include<cstdio>#include<cstring>#include< 查看详情
bzoj-2257:[jsoi2009]瓶子和燃料(中国剩余定理)
2257:[Jsoi2009]瓶子和燃料TimeLimit: 10Sec MemoryLimit: 128MBSubmit: 1583 Solved: 965[Submit][Status][Discuss]Descriptionjyy就一直想着尽快回地球，可惜他飞船的燃料不够了。 有一天他又去向火星人要 查看详情
bzoj1560jsoi2009火星藏宝图[dp]
火星藏宝图TimeLimit:10Sec MemoryLimit:64MB[Submit][Status][Discuss]Description Input Output SampleInput 410 1120 101010 3560 5330SampleOutput -4HINT 1<=M<=2000,2<=N<=100000 查看详情
bzoj1452:[jsoi2009]count
PS：c<=100（原谅像我一样眼瞎的人吧这题就是一个二维树状数组的模板啊，然后不会，然后学了学，然后好像没难度，自己看代码就会了。。#include<cstdio>#include<iostream>#include<cstring>#include<cstdlib>#include<algorith... 查看详情
bzoj1443[jsoi2009]游戏game
DescriptionInput输入数据首先输入两个整数N,M，表示了迷宫的边长。接下来N行，每行M个字符，描述了迷宫。Output若小AA能够赢得游戏，则输出一行"WIN"，然后输出所有可以赢得游戏的起始位置，按行优先顺序输出每行一个,否则输出... 查看详情
bzoj1558[jsoi2009]等差数列
传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1558【题解】这题恶心死人了啊。。网络上题解很多都是看代码看代码。。真是太不负责任了。。我这里详细说一下吧。。题解在代码下面。#include<stdio.h>#include<string.h>#include&... 查看详情
bzoj2257:[jsoi2009]瓶子和燃料数论：裴蜀定理
2257:[Jsoi2009]瓶子和燃料TimeLimit:10Sec MemoryLimit:128MBSubmit:1326 Solved:815[Submit][Status][Discuss]Descriptionjyy就一直想着尽快回地球，可惜他飞船的燃料不够了。有一天他又去向火星人要燃料，这次火星人答应了，要jyy用飞船... 查看详情
[bzoj1452][jsoi2009]count
来自FallDream的博客，未经允许，请勿转载，谢谢。 有一个n*m的矩阵，每个点有一个权值。需要支持两种操作：1)改变一个点的权值2)查询一个矩形内权值为c的个数n,m<=300q<=200000权值<=100权值有点小吧？那就每种权值开一... 查看详情
bzoj1443[jsoi2009]游戏game
AC通道:http://www.lydsy.com/JudgeOnline/problem.php?id=1443分析:对于这种棋子在棋盘上走来走去,只能走相邻的格子的问题,感觉还是挺好玩的... 然后好玩归好玩,可是有点不会做啊. 貌似棋盘上相邻格子这种不断移动的问题,都大概能... 查看详情
bzoj:1443:[jsoi2009]游戏game
原题链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1443反正不看题解我是完全想不出系列……先把棋盘黑白染色，也就是同一对角线上颜色相同，使得一个格子上下左右都不同色。然后我们会发现，某一个人所走的全部格子颜色都... 查看详情
bzoj2257:[jsoi2009]瓶子和燃料
Descriptionjyy就一直想着尽快回地球，可惜他飞船的燃料不够了。 有一天他又去向火星人要燃料，这次火星人答应了，要jyy用飞船上的瓶子来换。jyy的飞船上共有N个瓶子(1<=N<=1000)，经过协商，火星人只要其中的K个。jyy将K... 查看详情
bzoj2257:[jsoi2009]瓶子和燃料
Descriptionjyy就一直想着尽快回地球，可惜他飞船的燃料不够了。 有一天他又去向火星人要燃料，这次火星人答应了，要jyy用飞船上的瓶子来换。jyy的飞船上共有N个瓶子(1<=N<=1000)，经过协商，火星人只要其中的K个。jyy将K... 查看详情
bzoj1821jsoi2010group部落划分group
1821:[JSOI2010]Group部落划分GroupTimeLimit: 10Sec MemoryLimit: 64MBSubmit: 3064 Solved: 1449[Submit][Status][Discuss]Description聪聪研究发现，荒岛野人总是过着群居的生活，但是，并不是整个荒岛上的所 查看详情