比赛 |
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;
}