首页 > 代码库 > hdu 4467( 轻重点维护)
hdu 4467( 轻重点维护)
写了7000b代码 真是醉了#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#include <cctype>#include <complex>#include <cstring>#include <iomanip>#include <list>#include <map>#include <queue>#include <stack>#include <string>#include <vector>using namespace std;#define rep(i, n) for(int i=0; i<n; i++)#define fab(i, a, b) for(int i=(a); i<=(b); i++)#define PB push_back#define MP make_pair#define LL long long#define sf scanf#define pf printfconst int N = 110000;int n,m;int head[N],next[N*2],to[N*2];LL WW[N*2];int headW[N],nextW[N*2],toW[N*2];LL W[N*2];int used[N*2],col[N],d[N],isweight[N];LL weight[N][2];int e=0,eW;LL light0_0,light0_1,light1_1;LL weight0_0,weight0_1,weight1_1;vector<int>cal;int ecnt;void bug();struct Edge{ int u,v; LL w; Edge(int u=0,int v=0,LL w=0):u(u),v(v),w(w){} bool operator<(const Edge& rhs)const{ if(u!=rhs.u)return u<rhs.u; else if(v!=rhs.v)return v<rhs.v; else return w<rhs.w; }}E[N*2];void init(){ cal.clear(); e=eW=ecnt=0; light1_1=light0_0=light0_1=0; weight0_0=weight0_1=weight1_1=0; memset(used,0,sizeof used); memset(headW,-1,sizeof headW); memset(head,-1,sizeof head); memset(weight,0,sizeof weight); memset(d,0,sizeof d); memset(col,0,sizeof col); memset(isweight,0,sizeof isweight);}void addedge(int u,int v,LL w){ d[v]++; to[e]=v; W[e]=w; next[e]=head[u]; head[u]=e++;}void addedgeW(int u,int v,LL w){ toW[eW]=v; WW[eW]=w; nextW[eW]=headW[u]; headW[u]=eW++;}void input(){ fab(i,1,n)sf("%d",&col[i]); rep(i,m){ used[i]=0; int u,v; LL w; sf("%d%d%I64d",&u,&v,&w); if(u>v)swap(u,v); E[i].u=u;E[i].v=v;E[i].w=w; //addedge(u,v,w); //addedge(v,u,w); } sort(E,E+m); ecnt=0; for(int i=1;i<m;i++){ if(E[i].u==E[ecnt].u&&E[i].v==E[ecnt].v)E[ecnt].w+=E[i].w; else{ ecnt++; E[ecnt].u=E[i].u; E[ecnt].v=E[i].v; E[ecnt].w=E[i].w; } } for(int i=0;i<=ecnt;i++){ addedge(E[i].u,E[i].v,E[i].w); addedge(E[i].v,E[i].u,E[i].w); }}void predo(){ int mid=sqrt(n+0.5); fab(i,1,n){ if(d[i]>mid){ isweight[i]=1; cal.PB(i); }else{ isweight[i]=0; } } fab(u,1,n){ if(isweight[u]){ for(int p=head[u];~p;p=next[p]){ int v=to[p]; if(isweight[v]&&v<u){ addedgeW(u,v,W[p]); continue; } LL w=W[p]; weight[u][col[v]]+=w; if(col[u]!=col[v])weight0_1+=w; else{ if(col[u])weight1_1+=w; else weight0_0+=w; } } }else{ for(int p=head[u];~p;p=next[p]){ int v=to[p]; if(isweight[v]||v<u)continue; LL w=W[p]; if(col[v]!=col[u]){ light0_1+=w; }else{ if(col[u])light1_1+=w; else light0_0+=w; } } } }}void Change(int x){ if(isweight[x]){ if(col[x]){ weight0_1-=weight[x][0]; weight1_1-=weight[x][1]; weight0_1+=weight[x][1]; weight0_0+=weight[x][0]; }else{ weight0_1-=weight[x][1]; weight0_0-=weight[x][0]; weight1_1+=weight[x][1]; weight0_1+=weight[x][0]; } for(int p=headW[x];~p;p=nextW[p]){ int v=toW[p]; LL w=WW[p]; weight[v][col[x]]-=w; weight[v][col[x]^1]+=w; if(col[v]!=col[x]){ weight0_1-=w; if(col[x]==0)weight1_1+=w; else weight0_0+=w; }else{ if(col[x])weight1_1-=w; else weight0_0-=w; weight0_1+=w; } } }else{ for(int p=head[x];~p;p=next[p]){ int v=to[p]; LL w=W[p]; if(isweight[v]){ weight[v][col[x]]-=w; weight[v][col[x]^1]+=w; int a=col[v],b=col[x]; if(a!=b){ weight0_1-=w; if(b)weight0_0+=w; else weight1_1+=w; }else{ if(a)weight1_1-=w; else weight0_0-=w; weight0_1+=w; } }else{ if(col[x]!=col[v]){ light0_1-=w; if(col[x])light0_0+=w; else light1_1+=w; } else { if(col[x]==0){ light0_0-=w; }else { light1_1-=w; } light0_1+=w; } } } } col[x]^=1;}void Asksum(int a,int b){ LL ans=0; if(a!=b){ ans=light0_1+weight0_1; }else{ if(a)ans=light1_1+weight1_1; else ans=light0_0+weight0_0; }/* if(a!=b)ans=light0_1; else if(a)ans=light1_1+weight1_1; else ans=light0_0+weight0_0; rep(i,cal.size()){ int u=cal[i]; if(a==0&&b==0){ if(col[u]==0)ans+=weight[u][0]; }else if((a==0&&b==1)||(a==1&&b==0)){ ans+=weight[u][col[u]^1]; }else if(a==1&&b==1){ if(col[u])ans+=weight[u][1]; } }*/ pf("%I64d\n",ans);}void solve(){ int Q; sf("%d",&Q); char op[20]; int a,b; while(Q--){ // bug(); sf("%s",op); if(op[0]==‘A‘){ sf("%d%d",&a,&b); Asksum(a,b); }else if(op[0]==‘C‘){ sf("%d",&a); Change(a); } }}void bug(){ puts("bug"); /*fab(i,1,n){ pf("is i = %d weight %d\n",i,isweight[i]); }*/ pf("light 0_0 = %I64d 0_1 = %I64d 1_1 = %I64d\n",light0_0,light0_1,light1_1); pf("weight 0_0 = %I64d 0_1 = %I64d 1_1 = %I64d\n",weight0_0,weight0_1,weight1_1); fab(i,1,n){ if(isweight[i]){ pf(" wieght i= %d:\n",i); pf(" --0 = %I64d | ---1 = %I64d \n",weight[i][0],weight[i][1]); } } /* fab(i,1,n){ pf("i = %d :\n",i); for(int p=headW[i];~p;p=nextW[p])pf("%d ",to[p]);puts(""); }*/}int main() { //freopen("in","r",stdin); //freopen("mywa","w",stdout); int cas=1; while(~sf("%d%d",&n,&m)){ pf("Case %d:\n",cas++); init(); input(); predo(); // bug(); solve(); } return 0;}
hdu 4467( 轻重点维护)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。