https://ac.nowcoder.com/acm/contest/113/E

Code: 

#include 
     
      #include 
      
       #include 
       
        #define setIO(s) freopen(s".in","r",stdin) #define maxn 200005 #define inf 1000000009#define ll long long  using namespace std;      int top;   int S[maxn];ll le[maxn],ri[maxn],sumv[maxn];     struct Node {    ll x,y; }nd[maxn];      bool cmp(Node a,Node b) {    return a.x
        
         =1;--i) {         if(nd[i].y>0) sumv[i]+=nd[i].y;          ri[i]=ri[i+1];         if(nd[i+1].x!=nd[i].x) ri[i]=sumv[i+1];           }     for(int i=1;i<=n;++i) insert(i);     return 0;   }
        
       
      
     

　　

Code: 

#include
     
      using namespace std; void setIO(string s) {    string in=s+".in";     freopen(in.c_str(),"r",stdin); }const int maxn=200005;  struct Edge {    int u,v,c,i;     Edge(int u=0,int v=0,int c=0,int i=0):u(u),v(v),c(c),i(i){} }; bool cmp(Edge a,Edge b) {    return a.c
      
       G[maxn]; map
       
        id[maxn]; int n,m,cnt,edges; int hd[maxn],to[maxn<<1],nex[maxn<<1],val[maxn<<1]; void addedge(int u,int v,int c) {    nex[++edges]=hd[u],hd[u]=edges,to[edges]=v,val[edges]=c;   }int main() {    setIO("input");     scanf("%d%d",&n,&m);     for(int i=1;i<=m;++i) {        int u,v,c;         scanf("%d%d%d",&u,&v,&c);            G[u].push_back(Edge(u,v,c,i));         G[v].push_back(Edge(v,u,c,i));             id[u][i]=++cnt, id[v][i]=++cnt;     }     for(int i=1;i<=n;++i) {          sort(G[i].begin(),G[i].end(),cmp);          for(int j=0;j
        
         0) {                 addedge(id[G[i][j].u][G[i][j].i], id[G[i][j-1].u][G[i][j-1].i], 0);                                 addedge(id[G[i][j-1].u][G[i][j-1].i], id[G[i][j].u][G[i][j].i], G[i][j].c-G[i][j-1].c);                      }                                       addedge(id[G[i][j].u][G[i][j].i],id[G[i][j].v][G[i][j].i],G[i][j].c);            }             }      return 0;      }