qzezoj 1750 国王饮水记

当然这道题可以跑最小生成树。 但是那样时间复杂度是$O(nm\alpha (n))$，可以被卡掉。 这里有一个跑不满$O(nm)$的 就是每次拿到一条边，就搜索是否联通。 不连通就加上去 联通就找到最大的那条边，看看能不能替换，能换就换。 代码实现:

#include<cstdio> #include<cstring> #define max(a,b) ((a)>(b)?(a):(b)) using namespace std; int n,m,k,x,y,z,nowx,nowy,flags,flag,cur; long long ans,nowans; struct yyy{int to,w,z,flag;}tmp; struct ljb{ int head,h[100039]; yyy f[200039]; inline void add(int x,int y,int z){ f[++head]=(yyy){y,z,h[x],0}; h[x]=head; } }s; inline void dfs(int x,int last,int w){ if(x==y) flag=w; if(flag) return; yyy tmp; for(cur=s.h[x];~cur;cur=tmp.z){ tmp=s.f[cur]; if(!tmp.flag&&tmp.to!=last)dfs(tmp.to,x,max(w,tmp.w)); } } inline void dfs2(int x,int last,int w){ if(x==y) flags=w; if(flags) return; yyy tmp; for(cur=s.h[x];~cur;cur=tmp.z){ tmp=s.f[cur]; if(!tmp.flag&&tmp.to!=last){ if(tmp.w==flag) {nowx=tmp.to,nowy=x;} dfs2(tmp.to,x,max(w,tmp.w)); if(flags){ if(tmp.w==flag) {nowx=tmp.to,nowy=x;} return; } } } } inline void dfss(int x,int last){ nowans++; yyy tmp; for(int cur=s.h[x];~cur;cur=tmp.z){ tmp=s.f[cur]; if(!tmp.flag&&tmp.to!=last) dfss(tmp.to,x); } } int main(){ freopen("1.in","r",stdin); freopen("1.out","w",stdout); memset(s.h,-1,sizeof(s.h)); register int i; scanf("%d%d",&n,&m); while(m--){ scanf("%d%d%d",&x,&y,&z); flag=0; dfs(x,0,0); if(flag>z||!flag){ if(!flag) {ans+=z;s.add(x,y,z);s.add(y,x,z);} else{ flags=0;nowx=nowy=0; dfs2(x,0,0); cur=s.h[nowx]; while(~cur){ tmp=s.f[cur]; if(tmp.to==nowy&&!tmp.flag) {s.f[cur].flag=1;break;} cur=tmp.z; } cur=s.h[nowy]; while(~cur){ tmp=s.f[cur]; if(tmp.to==nowx&&!tmp.flag){s.f[cur].flag=1;break;} cur=tmp.z; } ans+=z-flag;s.add(x,y,z);s.add(y,x,z); } } nowans=0; dfss(1,0); printf("%lld %lld\n",ans,nowans); } }