「East!_XVI」九尾妖狐

2015年4月4日4,3850

Background

某无良设计师伊泽瑞尔:刀妹太弱了,我们来增强阿狸吧。

Description

阿狸现在有 N 个技能,伊泽瑞尔要决定它们是 AD 技能还是AP技能。

因为出装不同,所以当一个技能是 AP 时,阿狸的爆发增加 ap_i,当一个技能是 AD 时,阿狸的爆发增加 ad_i。

有些技能配合可以打出伤害加成,这样阿狸的技能就可以被表示为一张无向图。当有关联的两个技能都是 AD 时,阿狸的爆发增加 AD_i,当两个技能都是 AP 时,阿狸的爆发增加 AP_i, 当两个技能不同类时阿狸的爆发减少 Ahr_i。

求阿狸最多增加多少爆发。

Input

第一行两个整数 N,M 表示阿狸有 N 个技能,无向图有 M 条边。

接下来 N 行每行两个整数 ap_i,ad_i。
接下来 M 行每行五个整数 u,v,AD_i,AP_i,Ahr_i。

Output

输出一行一个整数,表示阿狸的爆发最多增加多少。

Sample Input

10
1234 4321

Sample Output

4321

Data Constraint

序号	N	M
1	5	5
2	50	100
3	100000	0
4	500000	0
5	1000	3000
6	1000	3000
7	1000	3000
8	10000	40000
9	10000	40000
10	10000	40000

所有数据不爆long long且均为整数

After Problem

鉴于伊泽瑞尔的风筝能力太强,所以基兰把伊泽瑞尔的技能移除了,但是他的普通攻击被增加了粒子特效,现在伊泽瑞尔看起来更酷炫了。

题解

最小割同文理分科

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
ll read()
{
	ll 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;
}
int T,n,m,cnt=1;
int last[500005],h[500005],q[500005];
ll tot;
struct edge{
	int to,next,v;
}e[3000005];
void insert(int u,int v,ll w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;
}
bool bfs()
{
	int head=0,tail=1;
	q[0]=0;
	for(int i=0;i<=T;i++)h[i]=-1;
	h[0]=0;
	while(head!=tail)
	{
		int now=q[head];head++;
		for(int i=last[now];i;i=e[i].next)
			if(h[e[i].to]==-1&&e[i].v)
			{
				h[e[i].to]=h[now]+1;
				q[tail++]=e[i].to;
			}
	}
	return h[T]!=-1;
}
int dfs(int x,int f)
{
	if(x==T)return f;
	int w,used=0;
	for(int i=last[x];i;i=e[i].next)
		if(h[e[i].to]==h[x]+1)
		{
			w=dfs(e[i].to,min(e[i].v,f-used));
			e[i].v-=w;e[i^1].v+=w;
			used+=w;if(used==f)return f;
		}
	if(!used)h[x]=-1;
	return used;
}
void dinic()
{
	while(bfs())tot-=dfs(0,inf);
}
int main()
{
	n=read();m=read();
	int now=n+1;
	T=n+2*m+1;
	int x;
	for(int i=1;i<=n;i++)
	{
		x=read();tot+=x;
		insert(0,i,x);
		x=read();tot+=x;
		insert(i,T,x);
	}
	ll u,v,ad,ap,ah;
	for(int i=1;i<=m;i++)
	{
		u=read();v=read();ad=read();ap=read();ah=read();
		tot+=ad+ap+2*ah-ah;
		insert(u,now,inf);
		insert(v,now,inf);
		insert(now,T,ad+ah);
		now++;
		insert(0,now,ap+ah);
		insert(now,u,inf);
		insert(now,v,inf);
		now++;
	}
	dinic();
	cout<<tot<<endl;
	return 0;
}

100

#include<set>

#include<map>

#include<ctime>

#include<queue>

#include<cmath>

#include<cstdio>

#include<vector>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

ll read()

{

ll 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;

}

int T,n,m,cnt=1;

int last[500005],h[500005],q[500005];

ll tot;

struct edge{

int to,next,v;

}e[3000005];

void insert(int u,int v,ll w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=0;

}

bool bfs()

{

int head=0,tail=1;

q[0]=0;

for(int i=0;i<=T;i++)h[i]=-1;

h[0]=0;

while(head!=tail)

{

int now=q[head];head++;

for(int i=last[now];i;i=e[i].next)

if(h[e[i].to]==-1&&e[i].v)

{

h[e[i].to]=h[now]+1;

q[tail++]=e[i].to;

}

return h[T]!=-1;

}

int dfs(int x,int f)

{

if(x==T)return f;

int w,used=0;

for(int i=last[x];i;i=e[i].next)

if(h[e[i].to]==h[x]+1)

{

w=dfs(e[i].to,min(e[i].v,f-used));

e[i].v-=w;e[i^1].v+=w;

used+=w;if(used==f)return f;

}

if(!used)h[x]=-1;

return used;

}

void dinic()

{

while(bfs())tot-=dfs(0,inf);

}

int main()

{

n=read();m=read();

int now=n+1;

T=n+2*m+1;

int x;

for(int i=1;i<=n;i++)

{

x=read();tot+=x;

insert(0,i,x);

x=read();tot+=x;

insert(i,T,x);

}

ll u,v,ad,ap,ah;

for(int i=1;i<=m;i++)

{

u=read();v=read();ad=read();ap=read();ah=read();

tot+=ad+ap+2*ah-ah;

insert(u,now,inf);

insert(v,now,inf);

insert(now,T,ad+ah);

now++;

insert(0,now,ap+ah);

insert(now,u,inf);

insert(now,v,inf);

now++;

}

dinic();

cout<<tot<<endl;

return 0;

}

« 「BZOJ3894」文理分科「BZOJ1797」[Ahoi2009] Mincut 最小割 »

hzwer.com _ Home | http://hzwer.com

「East!_XVI」九尾妖狐

分类目录

热门文章

Myfriends

近期评论