CF1266D/E

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
",tot);
	fo(i,1,tot)
	printf("%I64d %I64d %I64d
",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
",ans);
	}
}