传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=1449
题目简述：
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
题解：
设x为win，y为lose；
先让所有人后面比赛都会输，计算出一个preans，那么怎么处理会赢的请况呢？
很简单，就让一个人的win+1，lose-1，那么相对于之前就可以获得（c*(x+1)^2+d*（y-1）^2-c*x^2-d*y^2=2*c[i]*win[i]+c[i]+d[i]-2*d[i]*lose[i])
所以就在建一条这样的边就好了，推荐使用 zkw（速度快，代码短）；
1 #include<iostream>
2 #include<cstring>
3 #include<cstdio>
4 #define inf 0x7fffffff
5 #define maxn 1000000
6 int pre[maxn],v[maxn],cost[maxn],cap[maxn],lis[maxn];
7 int lose[
6010],win[
6010],
in[
6010],c[
6010],d[
6010],dis[
6010],now[
6010],sla[
6010],mark[
6010];
8 bool vis[
6010];
9 int n,m,s,t,tot,ans;
10 using namespace std;
11 void ins(
int a,
int b,
int c,
int d)
12 {
13 tot++; pre[tot]=now[a]; now[a]=tot; v[tot]=b; cost[tot]=d; cap[tot]=
c;
14 }
15 void insert(
int a,
int b,
int c,
int d)
16 {
17 ins(a,b,c,d); ins(b,a,
0,-
d);
18 }
19 bool spfa()
20 {
21 int head=
0,tail=
1;
22 for (
int i=s; i<=t; i++) dis[i]=
inf;
23 memset(mark,
0,
sizeof(mark));
24 lis[
0]=t; dis[t]=
0; mark[t]=
1;
25 while (head!=
tail)
26 {
27 int x=lis[head]; mark[x]=
0; head++
;
28 if(head==
6005)head=
0;
29 for (
int i=now[x]; i; i=
pre[i])
30 {
31 if (dis[x]+cost[i^
1]<dis[v[i]] && cap[i^
1])
32 {
33 dis[v[i]]=dis[x]+cost[i^
1];
34 if (!
mark[v[i]])
35 {
36 mark[v[i]]=
1;
37 tail++
;
38 lis[tail]=
v[i];
39 if(tail==
6005)tail=
0;
40 }
41 }
42 }
43 }
44 // printf("%d\n",dis[s]);
45 if (dis[s]!=inf )
return true;
else return false;
46 }
47 int dfs(
int x,
int f)
48 {
49 mark[x]=
1;
50 if (x==t)
return f;
51 int w,used=
0;
52 for (
int i=now[x]; i; i=
pre[i])
53 {
54 if (!mark[v[i]] && cap[i] && dis[x]-cost[i]==
dis[v[i]])
55 {
56 w=dfs(v[i],min(f-
used,cap[i]));
57 cap[i]-=w; cap[i^
1]+=
w;
58 ans+=w*
cost[i];
59 used+=w;
if (used==f)
return f;
60 }
61 }
62 return used;
63 }
64 void zkw()
65 {
66 while(spfa())
67 {
68 mark[t]=
1;
69 while(mark[t])
70 {
71 memset(mark,
0,
sizeof(mark));
72 dfs(s,inf);
73 }
74 }
75 }
76 int main()
77 {
78 scanf(
"%d%d",&n,&m); tot=
1; ans=
0;
79 for (
int i=
1; i<=n; i++
)
80 scanf(
"%d%d%d%d",&win[i],&lose[i],&c[i],&
d[i]);
81 s=
0; t=n+m+
1;
82 for (
int i=
1; i<=m; i++
)
83 {
84 int u,v;
85 insert(s,i,
1,
0);
86 scanf(
"%d%d",&u,&
v);
87 insert(i,u+m,
1,
0);
88 insert(i,v+m,
1,
0);
89 in[u]++;
in[v]++
;
90 }
91 for (
int i=
1; i<=n; i++
)
92 {
93 lose[i]+=
in[i];
94 }
95 ans=
0;
96 for(
int i=
1;i<=n;i++
)
97 ans+=win[i]*win[i]*c[i]+lose[i]*lose[i]*
d[i];
98 for (
int i=
1; i<=n; i++
)
99 for (
int j=
1; j<=
in[i]; j++
)
100 {
101 //insert(i+m,t,1,c[i]*(2*win[i]+2*j-1)-d[i]*(2*lose[i]-2*j+1));
102 insert(i+m,t,
1,
2*c[i]*win[i]+c[i]+d[i]-
2*d[i]*
lose[i]);
103 win[i]++; lose[i]--
;
104 }
105 //printf("%d\n",ans);
106 zkw();
107 printf(
"%d\n",ans);
108 return 0;
109 }
110
转载请注明原文地址: https://ju.6miu.com/read-1300403.html
