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) {新聞熱點
疑難解答
