【题目描述】
天上红绯在游戏中扮演敏剑，对于高攻击低防御的职业来说，爆发力显得非常重要，为此，她准备学习n个技能，每个技能都有2个学习方向：物理攻击和魔法攻击。对于第i个技能，如果选择物理攻击方向，会增加ap_i的爆发力，如果选择魔法攻击的方向，会增加ad_i的爆发力。此外，还有一些combo，一个combo由两个技能组成，对于第i个combo，如果他们都是魔法攻击，会额外增加AD_i的爆发力，如果他们都是物理攻击，会额外增加AP_i的爆发力，如果他们不属于同一类型，会减少AX_i的爆发力。她找到了你，请你帮她选择技能的类型，产生最大的爆发力。(说明：每个技能都必须学习)
【输入数据】
第一行2个正整数n,m，表示技能的个数和combo的个数
接下来n行每行2个正整数，描述一个技能的ap_i，ad_i
接下来m行每行5个正整数u,v,AD_i,AP_i,AX_i，描述一个combo，表示技能u和技能v产生combo
【输出数据】
一行，一个整数，表示最大的爆发力
【样例输入】
【样例输出】
【样例解释】
均选择魔法攻击，获得5+20+100=125的爆发力
【数据范围】
|
测试点编号 |
n |
m |
|
1 |
5 |
5 |
|
2 |
50 |
100 |
|
3 |
100000 |
0 |
|
4 |
500000 |
0 |
|
5-7 |
1000 |
3000 |
|
8-10 |
10000 |
40000 |
对于所有的测试点，确保不会爆long long
Solution
模型：最小割，最大权闭合子图
来自出题者的题解：可以先看作我们把所有的技能的收益（不包括亏损AX）都获得了，然后在这个获益中扣除最小的代价
建图：
对于每个技能，建边(S,u,ap)，(u,T,ad)
对于每个combo，拆点，对点一建边(S,buf1,AD)，(buf1,u,+∞)，(buf1,v,+∞)
对点二建边(buf2,T,AP)，(u,buf2,+∞)，(v,buf2,+∞)
跑个最大流算法就行
#include<stdio.h>
#include<limits.h>
#include<string.h>
#define LL long long
#define dmin(a,b) ((a)<(b)?(a):(b))
inline int Rin(){
int x=,c=getchar(),f=;
for(;c<||c>;c=getchar())
if(!(c^))f=-;
for(;c>&&c<;c=getchar())
x=(x<<)+(x<<)+c-;
return x*f;
}
const int N=;
const int M=;
const LL LINF=LONG_LONG_MAX/*;
LL tot();
int n,m,S,T,ecnt=,fst[N+M*];
struct edge{
int u,v,nxt;
LL cap,flow;
}e[(*M+*N)*];
inline void link(int x,int y,LL w){
e[++ecnt].u=x;e[ecnt].v=y;
e[ecnt].cap=w;e[ecnt].flow=;
e[ecnt].nxt=fst[x];fst[x]=ecnt;
e[++ecnt].u=y;e[ecnt].v=x;
e[ecnt].cap=;e[ecnt].flow=;
e[ecnt].nxt=fst[y];fst[y]=ecnt;
}
bool vis[N+M*];
int num[N+M*],cur[N+M*],d[N+M*],p[N+M*],q[N+M*];
void bfs(){
int hd=,tl=;
q[]=T;d[T]=;vis[T]=true;
while(hd^tl){
int now=q[hd++];
for(int j=fst[now];j;j=e[j].nxt)
if(!vis[e[j].u] && e[j].cap>e[j].flow)
vis[e[j].u]=true,
d[e[j].u]=d[now]+,
q[tl++]=e[j].u;
}
}
inline LL Agument(){
LL a=LINF;
int x=T;
while(x^S)
a=dmin(a,e[p[x]].cap-e[p[x]].flow),
x=e[p[x]].u;
x=T;
while(x^S)
e[p[x]].flow+=a,
e[p[x]^].flow-=a,
x=e[p[x]].u;
return a;
}
LL ISAP(){
int x(S);
LL flow();
bfs();
for(int i=S;i<=T;i++)num[d[i]]++;
for(int i=S;i<=T;i++)cur[i]=fst[i];
while(d[S]<T){
if(!(x^T))
flow+=Agument(),
x=S;
bool advanced=false;
for(int j=cur[x];j;j=e[j].nxt)
if(e[j].cap>e[j].flow && d[x]==d[e[j].v]+){
advanced=true;
cur[x]=j;
p[e[j].v]=j;
x=e[j].v;
break;
}
if(!advanced){
int mn=T-;
for(int j=fst[x];j;j=e[j].nxt)
if(e[j].cap>e[j].flow)
mn=dmin(mn,d[e[j].v]);
if(--num[d[x]]==)break;
num[d[x]=mn+]++;
cur[x]=fst[x];
if(x^S)x=e[p[x]].u;
}
}
return flow;
}
int main(){
freopen("skill.in","r",stdin);
freopen("skill.out","w",stdout);
n=Rin(),m=Rin();
S=,T=n++m*+;
for(int i=;i<=n;i++){
LL ap=Rin(),ad=Rin();
tot+=ap+ad;
link(S,i+,ap);
link(i+,T,ad);
}
for(int i=;i<=m;i++){
int u=Rin(),v=Rin();
LL AP=Rin(),AD=Rin(),AX=Rin();
tot+=AP+AD;
link(u+,v+,AX);
link(v+,u+,AX);
link(S,n++i,AD);
link(n++i,u+,LINF);
link(n++i,v+,LINF);
link(n++i+m,T,AP);
link(u+,n++i+m,LINF);
link(v+,n++i+m,LINF);
}
printf("%I64d\n",tot-ISAP());
fclose(stdin);
fclose(stdout);
return ;
}