比赛 20160415 评测结果 WAAAAWWAAW
题目名称 能量网络 最终得分 60
用户昵称 collor 运行时间 0.100 s
代码语言 C++ 内存使用 4.88 MiB
提交时间 2016-04-15 11:39:49
显示代码纯文本
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long LL;
const int maxn=1100,maxm=50500;
struct node
{
	int y,v,next;
}e[maxm],g[maxm];
int n,m,len=0,tot=0,ans=0x7F7F7F7F;
int linkk[maxn],linkg[maxn];
int a[maxn],b[maxn],mapp[maxn][maxn];
bool TNT[maxn];
int read()
{
	int x=0; char ch=getchar();
	while (ch<'0'||ch>'9')ch=getchar();
	while (ch>='0'&&ch<='9'){
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x;
}
inline void insert(int xx,int yy,int vv)
{
	e[++len].next=linkk[xx]; e[len].y=yy;
	e[len].v=vv; linkk[xx]=len;
}
inline void inserte(int xx,int yy,int vv)
{
	g[++tot].next=linkg[xx]; g[tot].y=yy;
	g[tot].v=vv; linkg[xx]=tot;
}
void init()
{
	memset(TNT,true,sizeof(TNT));
	memset(mapp,-1,sizeof(mapp));
	n=read(); m=read();
	for (int i=1;i<=n;i++)a[i]=read();
	for (int i=1;i<=n;i++)b[i]=read();
	for (int i=1;i<=m;i++){
		int xx=read(); int yy=read();
		if (mapp[xx][yy]<0){
			mapp[xx][yy]=a[yy];
			insert(xx,yy,a[yy]);
			inserte(yy,xx,a[yy]);
		}
	}
}
void dfs(int d,int k)
{
	if (d==n)return ;
	//for (int i)
}
int main()
{
	freopen("energynet.in","r",stdin);
	freopen("energynet.out","w",stdout);
	int mint=0;
	init();
	for (int i=1;i<=n;i++){//高压放电!!!
		int sum=0;
		for (int j=linkg[i]; j ;j=g[j].next)
			sum+=g[j].v;
		if (sum>b[i])TNT[i]=0,mint+=b[i];
	}
	for (int i=1;i<=n;i++){
		int maxt=0,id=0,tc=0;
		for (int j=linkk[i]; j ;j=e[j].next){
			int tm=e[j].y;
			if (tc<e[j].v)tc=e[j].v,id=tm;
			if (TNT[tm]){
				if (maxt<e[j].v)maxt=e[j].v;
			}
		}
		mint+=maxt;
	}
	cout<<mint<<'\n';
	return 0;
}