D

题意：

一个有向图，每次可以选两条边权为u和v的边a->b,c->d（u,v>0）,把a->b,c->d减min(u,v)，把a->d,c->b加min(u,v)

求一种变化后的情况，使得总剩余边权和最小

题解：

可以发现无论怎样操作，每个点的 总入-总出 是不变的

所以求出 总入-总出 ，用负的向正的连边即可

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

struct type{
    long long s;
    int id;
} a[100001];
long long ans[300001][3];
int n,m,i,j,k,l,tot;

bool cmp(type a,type b)
{
    return a.s<b.s;
}

int main()
{
//  freopen("d.in","r",stdin);
    
    scanf("%d%d",&n,&m);
    fo(i,1,n) a[i].id=i;
    fo(i,1,m)
    {
        scanf("%d%d%d",&j,&k,&l);
        
        a[j].s-=l;
        a[k].s+=l;
    }
    
    sort(a+1,a+n+1,cmp);
    
    i=1;j=n;
    while (i<j && !a[i].s) ++i;
    while (i<j && !a[j].s) --j;
    
    while (i<j)
    {
        if (a[i].s+a[j].s>0)
        {
            ++tot;
            ans[tot][0]=a[i].id;
            ans[tot][1]=a[j].id;
            ans[tot][2]=abs(a[i].s);
            
            a[i].s+=ans[tot][2];
            a[j].s-=ans[tot][2];
        }
        else
        {
            ++tot;
            ans[tot][0]=a[i].id;
            ans[tot][1]=a[j].id;
            ans[tot][2]=abs(a[j].s);
            
            a[i].s+=ans[tot][2];
            a[j].s-=ans[tot][2];
        }
        
        while (i<j && !a[i].s) ++i;
        while (i<j && !a[j].s) --j;
    }
    
    printf("%d\n",tot);
    fo(i,1,tot)
    printf("%I64d %I64d %I64d\n",ans[i][0],ans[i][1],ans[i][2]);
}

E

一个游戏，有n种资源，每个时刻可以生产一个任意资源，给出每种资源的目标a

有若干成就(s,t,u)，表示资源s到达t时会获得一个资源u，保证t<a[s]且不存在任意两个s和t的成就

支持动态修改成就，求最小时间

题解：

因为没看到st不同所以暴毙

ans至少为Σmax(ai-Σ[u=i],0)，现证明可以达到

如果不能达到，则必然存在某个时刻满足 没有达到要求并且无法获得新的资源

注意到t<a[s]，所以每种资源都空了一个位置

所以画一下发现不存在，证毕

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <map>
#include <set>
#define fo(a,b,c) for (a=b; a<=c; a++)
#define fd(a,b,c) for (a=b; a>=c; a--)
#define max(a,b) (a>b?a:b)
//#define file
using namespace std;

map<long long,int> Hash;
map<long long,int> :: iterator I;
int a[200001];
int b[200001];
int Q,n,i,j,k,l,s,t,u;
long long ans;

int main()
{
    #ifdef file
    freopen("CF1266E.in","r",stdin);
    #endif
    
    scanf("%d",&n);
    fo(i,1,n)
    scanf("%d",&a[i]),ans+=a[i];
    
    scanf("%d",&Q);
    for (;Q;--Q)
    {
        scanf("%d%d%d",&s,&t,&u);
        
        I=Hash.find(1ll*s*10000000000ll+t);
        if (I!=Hash.end())
        {
            ans-=max(a[I->second]-b[I->second],0);
            --b[I->second];
            ans+=max(a[I->second]-b[I->second],0);
            
            Hash.erase(I);
        }
        
        Hash.insert(pair<long long,int>(1ll*s*10000000000ll+t,u));
        ans-=max(a[u]-b[u],0);
        ++b[u];
        ans+=max(a[u]-b[u],0);
        
        printf("%I64d\n",ans);
    }
}

CF1266D/E

原文：https://www.cnblogs.com/gmh77/p/12116607.html