C++14(g++5.4) 解法, 执行用时: 4350ms, 内存消耗: 44500K, 提交时间: 2019-08-07 16:23:11

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 1e5 + 5;
int T;
 
int n, m, k;
 
int u[N], v[N], c[N];
int p[N];
 
struct node {
    int v;
    LL m;
    int t;
    bool operator < (const node &rhs) const {
        if(m != rhs.m) return m > rhs.m;
        if(t != rhs.t) return t > rhs.t;
        return v > rhs.v;
    }
    bool operator == (const node &rhs) const {
        return v == rhs.v && m == rhs.m && t == rhs.t;
    }
    node(int _v=0, LL _m=0, int _t=-1):v(_v),m(_m),t(_t) { }
};
 
map<int,node> mp[N];
set<node> S[N];
int ans;
 
inline int get(int x) {
    return S[x].size() ? S[x].begin()->v : 0;
}
inline int check(int u) {
    return p[u] != 0 && p[p[u]] != u;
}
void add(int u, int v, int w, int t) {
    node &m1 = mp[u][v], &m2 = mp[v][u];
    m1.v = v; m2.v = u;
    S[u].erase(m1);
    S[v].erase(m2);
     
    m1.m += w;
    m1.t = max(m1.t, t);
    m2.m += w;
    m2.t = max(m2.t, t);
 
    if(m1.m > 0) S[u].insert(m1);
    if(m2.m > 0) S[v].insert(m2);
 
    set<int> g({u, v, p[u], p[v], get(u), get(v)});
    g.erase(0);
 
    for(int x : g) {
        if(check(x)) --ans;
    }
    for(int x : g) {
        p[x] = get(x);
    }
    for(int x : g) {
        if(check(x)) ++ans;
    }
}
 
int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d%d", &n, &k, &m);
        for(int i = 1; i <= n; ++i) {
            p[i] = 0;
            mp[i].clear();
            S[i].clear();
        }
        ans = 0;
        for(int i = 0; i < k; ++i) {
            if(i >= m) {
                add(u[i-m], v[i-m], -c[i-m], i-m);
            }
            scanf("%d%d%d", &u[i], &v[i], &c[i]);
            add(u[i], v[i], c[i], i);
            printf("%d\n", ans);
        }
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 5730ms, 内存消耗: 54648K, 提交时间: 2020-03-10 13:46:31

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
#define ll long long
#define N 100005
using namespace std;
int n,t,m,a[N],b[N],c[N],to[N],ans;
map<int,ll>cnt[N];
map<int,int>cur[N];
struct node
{
	ll v;
	int t,x;
};
bool operator<(node a,node b)
{
	if(a.v==b.v) return a.t<b.t;
	return a.v<b.v;
}
set<node>heap[N];
void update(int x,int y,int z,int T)
{
	int pre=to[x];
	node tmp;
	if(cnt[x].count(y))
	{
		tmp=node{cnt[x][y],cur[x][y],y};
		heap[x].erase(tmp);
	}
	cnt[x][y]+=z;
	cur[x][y]=max(cur[x][y],T);
	tmp=node{cnt[x][y],cur[x][y],y};
	if(tmp.v) heap[x].insert(tmp);
	if(heap[x].empty()) to[x]=0;
	else to[x]=(*--heap[x].end()).x;
	if(to[x]==pre) return;
	if(to[pre]==x) ans+=pre>0;
	else ans-=pre>0;
	if(to[to[x]]==x) ans-=to[x]>0;
	else ans+=to[x]>0; 
}
void modify(int x,int y,int z,int T)
{
	update(x,y,z,T);
	update(y,x,z,T);
}
void solve()
{
	int i;
	ans=0;
	scanf("%d%d%d",&n,&t,&m);
	for(i=1;i<=t;i++) scanf("%d%d%d",&a[i],&b[i],&c[i]);
	for(i=1;i<=n;i++) cnt[i].clear(),cur[i].clear(),heap[i].clear(),to[i]=0;
	for(i=1;i<=m&&i<=t;i++)
	{
		modify(a[i],b[i],c[i],i);
		printf("%d\n",ans);
	}
	for(i=m+1;i<=t;i++)
	{
		modify(a[i],b[i],c[i],i);
		modify(a[i-m],b[i-m],-c[i-m],i-m);
		printf("%d\n",ans);
	}
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)
	solve();
}