P2294 [HNOI2005] 狡猾的商人 两种做法

贪心

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=1e3+100;

int n,m;

struct NODE{
	int l,r,val;
	bool operator < (const NODE &h)const
	{
		if(l!=h.l)	return l>h.l;
		return r>h.r;
	}
};

priority_queue<NODE> q;

signed main()
{
	int T;
	cin>>T;
	while(T--)
	{
		while(q.size())	q.pop();
		cin>>n>>m;
		for(int i=1;i<=m;i++)
		{
			int l,r,val;
			cin>>l>>r>>val;
			q.push({l,r,val});
		}
		
		bool sg=false;
		
		auto tmp=q.top();
		q.pop();
		while(q.size())
		{
			auto tmp1=q.top();q.pop();
			if(tmp.l==tmp1.l)
			{
				if(tmp.r==tmp1.r)
				{
					if(tmp.val!=tmp1.val)
					{
						sg=true;
						break;
					}
				}
				else
					if(tmp.r<tmp1.r)
						q.push({tmp.r+1,tmp1.r,tmp1.val-tmp.val});
			}
			tmp=tmp1;
		}
		if(sg)	cout<<"false"<<endl;
		else	cout<<"true"<<endl;
	}
	
	return 0;
}

带权并查集

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=110;

int n,m;
int f[N],cha[N];

int find(int x)
{
	if(x!=f[x])
	{
		int t=find(f[x]);
		cha[x]+=cha[f[x]];
		f[x]=t;
	}
	return f[x];
}

signed main()
{
	int T;
	cin>>T;
	while(T--)
	{
		bool sg=false;
		cin>>n>>m;
		for(int i=0;i<=n;i++)	f[i]=i,cha[i]=0;
		for(int i=1;i<=m;i++)
		{
			int x,y,z;
			cin>>x>>y>>z;
			x--;
			if(find(x)!=find(y))
			{
				cha[f[y]]=cha[x]-cha[y]-z;
				f[f[y]]=f[x];
			}
			else
				if(cha[x]-cha[y]!=z)
				{
					sg=true;
					break;
				}
		}
		if(sg)	cout<<"false";
		else	cout<<"true";
		cout<<endl; 
	}
	return 0;
}

区间DP

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N=110;

int n,m;
int f[N][N];

signed main()
{
	int T;
	cin>>T;
	while(T--)
	{
		memset(f,0,sizeof f);
		cin>>n>>m;
		for(int i=1;i<=m;i++)
		{
			int x,y,z;
			cin>>x>>y>>z;
			f[x][y]=z;
		}
		bool sg=true;
		for(int i=2;i<=n;i++)
			if(sg)//加速
				for(int j=i-1;j>=1;j--)
					if(sg)//加速*2
						for(int k=j;k<i;k++)
							if(f[j][k] && f[k+1][i]) 
							{
								if(f[j][i])
								{
									if(f[j][i]!=f[j][k]+f[k+1][i])
									{
										sg=false;
										break;
									}
								}
								else
									f[j][i]=f[j][k]+f[k+1][i];
							}
		if(sg)	cout<<"true";
		else	cout<<"false";
		cout<<endl; 
	}
	return 0;
}