bzoj1449 [JSOI2009]球队收益

bzoj1449 [JSOI2009]球队收益

题目在这里(​​ Description Input Output 一个整数表示联盟里所有球队收益之和的最小值。 Sample Input 3 3 1 0 2 1 1 1 10 1 0 1 3 3 1 2 2 3 3 1 Sample Output 43 HINT

Source

qwq自己yy的做法全是错的 写一半就把自己否决了

什么也不说直接看题解吧 首先 这题特殊的一点在于如果输球了 我还是会get正的贡献 那么不妨我先把所有队伍初始状态 并且假设剩下的所有场全部都输了的费用计算出来 然后再建图跑一下最小费用流即可 这怎么跑呢 我们尝试思考 把每场比赛认为是一个点 然后从源点向这场比赛连容量1 费用0的边 然后这场比赛向两支队伍连边 容量是1 费用是0 然后每个人 根据他所赢得的比赛的场次 然后计算一下费用连到汇点 和之前的一题挺像的就是容量限制成1 但是费用给他拆开 然后跑费用流即可

#include#include#include#include#include#define pa pair #define N 7700#define inf 0x3f3f3f3fusing namespace std;inline char gc(){ static char now[1<<16],*S,*T; if (T==S){T=(S=now)+fread(now,1,1<<16,stdin);if (T==S) return EOF;} return *S++;}inline int read(){ int x=0;char ch=gc(); while(ch<'0'||ch>'9') ch=gc(); while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=gc(); return x;}int num=1,h[N],f[N],flag[N],pre[N],path[N],T,n,m,win[N],lose[N];struct node{ int y,z,next,c;}data[2200000];inline void insert1(int x,int y,int z,int c){ data[++num].y=y;data[num].z=z;data[num].c=c;data[num].next=h[x];h[x]=num; data[++num].y=x;data[num].z=0;data[num].c=-c;data[num].next=h[y];h[y]=num;}inline bool spfa(){ memset(f,0x3f,sizeof(f));memset(flag,0,sizeof(flag));memset(pre,-1,sizeof(pre));f[0]=0;flag[0]=1;queueq;q.push(0); while(!q.empty()){ int x=q.front();q.pop();flag[x]=0; for (int i=h[x];i;i=data[i].next){ int y=data[i].y,z=data[i].z,c=data[i].c; if (f[x]+c

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。