差分约束

2018-08-21

字数统计: 1.2k字 | 阅读时长: 6min

Layout

#include<cstdio>
#include<algorithm>
#include<queue>
#include<string>
#include<cstring>
#include<iostream>
using namespace std;
struct node
{
	int ne,to,w;
}edge[21000];
int head[11000],cnt;
void add(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].ne=head[u];
	edge[cnt].w=w;
	head[u]=cnt;
}
int n,ml,md,dis[11000],vis[11000];
int tot[11000];
int spfa(int s)
{
	memset(dis,0x3f,sizeof(dis)); 
	queue<int>q;
	q.push(s);
	dis[s]=0;
	vis[s]=1;
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to,w=edge[i].w;
			if(dis[u]+w<dis[v])
			{
				dis[v]=dis[u]+w;
				if(!vis[v])
				{
					q.push(v);
					vis[v]=1;
					tot[v]++;
					if(tot[v]>n) return -1;
				}
			}
		}
	}
	if(dis[n]==0x3f3f3f3f) return -2;
	return dis[n];
}
int main()
{
	scanf("%d %d %d",&n,&ml,&md);
	for(int i=1;i<=ml;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}	
	for(int i=1;i<=md;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add(v,u,-1*w);
	}
	cout<<spfa(1);
	return 0;
}

若是求最大的题，一般将其转换为a-b<=c，将b->a连一条边权为c的边，若答案有环，则无解，答案等于INF，无数解，否则唯一解。

candies

#include<queue>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
using namespace std;
int n,m;
struct node
{
	int ne,to,w;
}edge[150001];
int head[30001],cnt;
void add(int u,int v,int w)
{
	edge[++cnt].to=v;
	edge[cnt].ne=head[u];
	edge[cnt].w=w;
	head[u]=cnt;
}
int dis[30001],vis[30001];
void dj(int s)
{
	memset(dis,0x3f,sizeof(dis));
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
	q.push(make_pair(0,s));
	dis[1]=0;
	while(!q.empty())
	{
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=head[u];i;i=edge[i].ne)
		{
			int v=edge[i].to,w=edge[i].w;
			if(dis[u]+w<dis[v])
			{
				dis[v]=dis[u]+w;
				if(!vis[v])
				{
					q.push(make_pair(dis[v],v));
				}
			}
		}
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d %d %d",&u,&v,&w);
		add(u,v,w);
	}
	dj(1);
	printf("%d",dis[n]);
	return 0;
}

方块

【 问题描述】
方方方有着操控方块矩阵的能力， 它可以指定一个 n*m方块矩阵(初始时均为 0)中某一行或某一列方格的价值加 1 或减 1， fjzzq2002 觉得这样不行， 这样太无趣了。 
于是 fjzzq2002 给出了方方方 k 个限制， 每个限制为一个三元组(a,b,c)， 代表格子(a,b)在操作结束后的价值要等于 c， 然后询问方方方是否存在这样的操作序列满足他给出的限制。
方方方觉得 fjzzq2002 的要求太过分了， 于是向方老师求助。 方老师觉得这是一道好题， 于是交给了你。 如果存在输出” Yes” ， 否则输出” No” 。
【 输入格式】
第一行为一个正整数 T， 代表输入有 T 组数据。
对于每组数据第一行三个整数 n, m, k。
接下来 k 行， 每行三个整数 a, b, c。
【 输出格式】
对于每组数据， 输出 Yes 或者 No。
输入：            输出：

2               Yes
1 2 2           No
1 1 7
1 2 7
2 2 4
1 1 7
1 2 7
2 1 33
2 2 32

差分约束...完全不会做啊！qwq！，还好有正解。

#include<bits/stdc++.h>
using namespace std;
int T;
struct node{
    int ne,to,w;
}edge[100000];
int head[5000],cnt;     
int n,m,k;
void add(int u,int v,int w)
{
    edge[++cnt].to=v;
    edge[cnt].w =w;
    edge[cnt].ne=head[u];
    head[u]=cnt;
}
int cn[5000],vis[5000],dis[5000];
int spfa()
{
    queue<int> q;
    for(int i=1;i<=n+m;i++)
    {
        q.push(i);
        dis[i]=0;
        vis[i]=1;
        cn[i]=1;
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=head[u];i;i=edge[i].ne)
        {
            int v=edge[i].to,w=edge[i].w;
            if(dis[u]+w<dis[v])
            {
                dis[v]=dis[u]+w;
                if(!vis[v])
                {
                    q.push(v);
                    vis[v]=1;
                    cn[v]++;
                    if(cn[v]>n+m) return -1;
                }
            }
        }
    }
    return 0;
}
int main()
{
    freopen("matrix.in","r",stdin);
    freopen("matrix.out","w",stdout);
    scanf("%d",&T);
    for(int j=1;j<=T;j++)
    {
        memset(head,0,sizeof(head));
        cnt=0;
        scanf("%d %d %d",&n,&m,&k);
        for(int i=1;i<=k;i++)
        {
            int x,y,w;
            scanf("%d %d %d",&x,&y,&w);
            add(y+n,x,w);
            add(x,y+n,-w);
        }
        if(spfa()==-1) printf("No\n");
        else printf("Yes\n");
    }
    return 0;
}

将a+b=c化为a-(-b)<=c和(-b)-a<=-c,连边跑spfa，若无环，就是唯一解或无限解.否则输出NO，其中-b和b+n都是列b的编号。

夜深人静写算法（四） - 差分约束（%%%神佬，Orz）

本文作者： syrsteven
最后更新： 2023年09月02日 04:06:21
本文链接： http://syrsteven.github.io/post/417dcd30.html
版权声明： 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可，转载请注明出处！