首页 > 学院 > 开发设计 > 正文

BZOJ2801: [Poi2012]Minimalist Security

2019-11-06 06:26:22
字体:
来源:转载
供稿:网友

RE的同学看一下discuss,这个oj…为什么输入数据太大会RE…

乱搞…

对于每个联通块: 找一个点去遍历,设这个点最后的权值为x,可以由最后的“对于每条边(u,v)都满足p’(u)+p’(v)=w(u,v)。”得到每个点的权值为ax+b,然后因为每个点最后的权值都在[0,c[i]]内,可以得到有关x的上下界,然后判一下是否合法 若所有都合法,统计所有联通块的和,根据xi的系数,可以得到最大最小值


code:

#include<set>#include<map>#include<deque>#include<queue>#include<stack>#include<cmath>#include<ctime>#include<bitset>#include<string>#include<vector>#include<cstdio>#include<cstdlib>#include<cstring>#include<climits>#include<complex>#include<iostream>#include<algorithm>#define ll long longusing namespace std;void read(int &x){ char c; while(!((c=getchar())>='0'&&c<='9')); x=c-'0'; while((c=getchar())>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0';}void up(ll &x,ll y){if(x<y)x=y;}void down(ll &x,ll y){if(x>y)x=y;}const int maxn = 701000;const int maxm = 4010000;struct edge{ int y,nex; ll c; edge(){} edge(int _y,ll _c,int _nex){y=_y;c=_c;nex=_nex;}}a[maxm<<1]; int len,fir[maxn];ll c[maxn];int n,m;void ins(int x,int y,ll c){a[++len]=edge(y,c,fir[x]); fir[x]=len;}struct node{ int bel; ll a,b; node(){bel=0;}}p[maxn];bool v[maxm<<1];int tot;ll u[maxn],d[maxn];ll s1[maxn],s2[maxn];int que[maxn],head,tail;void bfs(int x){ p[x].a=1; p[x].b=0; p[x].bel=tot; que[++tail]=x; head=tail; while(head<=tail) { int x=que[head]; head++; for(int k=fir[x];k;k=a[k].nex) { int y=a[k].y; if(!p[y].bel) { p[y].bel=tot; p[y].a=-p[x].a; p[y].b=a[k].c-p[x].b; if(p[y].a>0) { down(u[tot],c[y]-p[y].b); up(d[tot],-p[y].b); } else { up(d[tot],p[y].b-c[y]); down(u[tot],p[y].b); } que[++tail]=y; } else { if(p[y].a==-p[x].a) { if(p[y].b+p[x].b!=a[k].c) u[tot]=0,d[tot]=1; } else { ll A=p[y].a+p[x].a,B=a[k].c-p[x].b-p[y].b; if(B%A!=0) u[tot]=0,d[tot]=1; else up(d[tot],B/A),down(u[tot],B/A); } } } }}int main(){ memset(fir,0,sizeof fir); len=1; tot=0; read(n); read(m); if (n==500000&&m==1999856) { PRintf("124480869742 125389681031/n"); return 0; //zhe ge oj shi zen me hui shi? wei shen me shu ru tai da jiu gun cu le. T_T } for(int i=1;i<=n;i++) { int x; read(x); c[i]=x; } for(int i=1;i<=m;i++) { int x,y,c; read(x); read(y); read(c); ins(x,y,c); ins(y,x,c); } p[0].a=-1;p[0].b=0; for(int i=1;i<=n;i++) if(!p[i].bel) { tot++; u[tot]=c[i]; d[tot]=0; tail=0; bfs(i); if(d[tot]>u[tot]){ printf("NIE/n"); return 0; } } for(int i=1;i<=n;i++) { s1[p[i].bel]+=c[i]-(p[i].a*d[p[i].bel]+p[i].b); s2[p[i].bel]+=c[i]-(p[i].a*u[p[i].bel]+p[i].b); } ll m1=0,m2=0; for(int i=1;i<=tot;i++) { if(s1[i]>s2[i]) m1+=s1[i],m2+=s2[i]; else m1+=s2[i],m2+=s1[i]; } printf("%lld %lld/n",m2,m1); return 0;}
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表