洛谷 P5590 赛车游戏
Problem
给一张有向图，请给每一条边赋上边权\(w\in[1,9]\)使得每一条\(1\to n\)的路径的长度相等。
Solution
先来点前置知识：差分约束。
简述
将很多对变量之间的差\(\le c\)的关系转化为图论，再用图论算法来求解这个不等式组的解。
步骤
对于\(x_j-x_i\le k\)，我们会发现它类似最短路网络中的三角不等式\(d_v-d_u\le w_{<u,v>}\).我们将每一个变量看作一个点，再建立一个超级原点\(x_0\)并向每一个点连一条权值为0的有向边。对于每一个不等式\(x-y\le k\to x\le y+k\)，我们连一条由\(y\)指向\(x\)，权值为\(k\)的有向边，然后跑最短路。
在建图的过程中要先关注具体问题，若求的是两个变量差的最大值，那么将所有不等式转变成"<="的形式并且在建图后求最短路，反之在转换成">="的形式，并且求最长路。
另外，如果有负环，那么该不等式组无解。我们只要放心大胆的跑SPFA就好。如果一个点入队次数大于\(n\)，说明存在负环。
Code
见模板题
好。接下来回到这道题。
给一张有向图，请给每一条边赋上边权\(w\in[1,9]\)使得每一条\(1\to n\)的路径的长度相等。
如果始终想的是如何让所有\(1\to n\)的路径相等那么就想错方向了。
在一个图中进行最短路的时候，\(dis_x+w_{x\to v}=dis_v\)说明\(dis_v-dis_x=w_{x\to v}\in[1,9]\)，这样我们才可以用差分约束系统进行求解。
\(1\le dis_v-dis_x\le9\longrightarrow dis_v\le dis_x+9\bigvee dis_x\le dis_v-1\)，所以我们连一条\(x\to v\)权值为9的边，一条\(v\to x\)权值为\(-1\)的边。
Code
/**************************************************************
* Problem: 5590
* Author: Vanilla_chan
* Date: 20210330
* E-Mail: Vanilla_chan@outlook.com
**************************************************************/
//预编译部分已略
#define N 2010
#define M 8000
int head[N],ver[M],nxt[M],w[M];
int cnt;
void insert(int x,int y,int z)
{
nxt[++cnt]=head[x];
head[x]=cnt;
ver[cnt]=y;
w[cnt]=z;
}
int f[N];
int getf(int x)
{
if(f[x]==x) return x;
return f[x]=getf(f[x]);
}
void merge(int x,int y)
{
x=getf(x);
y=getf(y);
if(x==y) return;
f[x]=y;
}
int n,m;
vector<int>edge[N],redge[N];
int u[N],v[N];
int useful[N];
bool book[N];
void dfs(int x)
{
if(book[x]) return;
book[x]=1;
useful[x]++;
for(unsigned int i=0,v;i<edge[x].size();i++)
{
v=edge[x][i];
dfs(v);
}
}
void rdfs(int x)
{
if(book[x]) return;
book[x]=1;
useful[x]++;
for(unsigned int i=0,v;i<redge[x].size();i++)
{
v=redge[x][i];
rdfs(v);
}
}
queue<int>q;
int dis[N];
int tot[N];
bool SPFA(int x)
{
while(q.size()) q.pop();
memset(dis,0x3f,sizeof(dis));
dis[x]=0;
memset(book,0,sizeof(book));
book[x]=1;
q.push(x);
while(q.size())
{
x=q.front();
q.pop();
book[x]=0;
for(int i=head[x],v;i;i=nxt[i])
{
v=ver[i];
if(dis[v]>dis[x]+w[i])
{
dis[v]=dis[x]+w[i];
if(!book[v])
{
tot[v]++;
if(tot[v]>n) return 0;
book[v]=1;
q.push(v);
}
}
}
}
return 1;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
n=read();
m=read();
for(int i=1;i<=m;i++)
{
u[i]=read();
v[i]=read();
edge[u[i]].push_back(v[i]);
redge[v[i]].push_back(u[i]);
merge(u[i],v[i]);
}
if(getf(1)!=getf(n))
{
cout<<"-1"<<endl;
return 0;
}
for(int i=1;i<=n;i++) useful[i]=-1;
dfs(1);
memset(book,0,sizeof(book));
rdfs(n);
memset(book,0,sizeof(book));
for(int i=1;i<=n;i++)
{
if(useful[i]!=1) useful[i]=0;
}
if(useful[1]==0||useful[n]==0)
{
cout<<"-1"<<endl;
return 0;
}
for(int i=1;i<=m;i++)
{
if(useful[u[i]]&&useful[v[i]])
{
insert(u[i],v[i],9);
insert(v[i],u[i],-1);
}
}
if(SPFA(1)==0)
{
cout<<"-1"<<endl;
return 0;
}
cout<<n<<" "<<m<<endl;
for(int i=1;i<=m;i++)
{
cout<<u[i]<<" "<<v[i]<<" ";
if(useful[u[i]]&&useful[v[i]])
{
cout<<dis[v[i]]-dis[u[i]];
}
else cout<<rand()%9+1;
cout<<endl;
}
return 0;
}