首页 > 代码库 > 【差分约束系统】【强连通分量缩点】【拓扑排序】【DAG最短路】CDOJ1638 红藕香残玉簟秋，轻解罗裳，独上兰舟。
【差分约束系统】【强连通分量缩点】【拓扑排序】【DAG最短路】CDOJ1638 红藕香残玉簟秋，轻解罗裳，独上兰舟。
题意： 给定n个点（点权未知）和m条信息：u的权值>=v的权值+w 求点权的极小解和极大解（无解则输出-1）
极小解即每个点的点权可能的最小值 极大解即每个点的点权可能的最大值
题解： 差分约束系统
对于val[u]>=val[v]+w 要得到极小解，v是没有受限制的，其最小值为0 而u受到v的限制，显然，val[u]的最小值就是val[v]+w
在多条件限制下，我们用v连向u边权为w的边表示每个限制条件val[u]>=val[v]+w 那么如果得到的是拓扑图，则按拓扑序求到每个点的最长路，就得到极小解
如果得到的不是拓扑图，即图中存在回路 那么如果存在回路边权和>0，则无解（成立的前提是边权都是大于等于零的）
总的来说，求极小解的做法就是，先对val[u]>=val[v]+w建立v连向u边权为w的边 对得到的图求强连通分量，将每个强连通分量缩成一个点 若存在边权和>0的强连通分量，则无解
否则在缩点后的拓扑图上，从入度为0的点出发按拓扑序求到每个点的最长路 该最长路就是每个点的最小值
不缩点直接判是否有回路，没有回路再拓扑，这样做会出错 因为会有边权和为0的强连通分量
对于求极大解，则将条件写成val[v]<=val[u]-w的形式 建立u连向v边权为-w的边，同样求强连通分量并缩点 在缩点后的拓扑图上做最短路，该最短路就是每个点的最大值
差分约束系统如果要求最优解而非合法解，并且整个图不能转化成从某个特定点出发的话。需要进行缩点+拓扑排序……往往只在边权都大于零或者都小于零的时候才成立。
因为对于多起点的情况而言，spfa判负环是失效的，互相制约的关系也很难通过添加虚拟结点来弥补。
#include<cstdio>
#include<vector>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
int us[1000010],vs[1000010],ws[1000010];
struct Edge{
int v,w;
};
vector<Edge>G[100010];
vector<int>rG[100010],tv;
bool used[100010];
int cmp[100010];
int ru[100010],f[100010],ansa[100010];
int n,m;
void AddEdge(int U,int V,int W){
G[U].push_back((Edge){V,W});
rG[V].push_back(U);
}
void dfs(int U){
used[U]=1;
for(int i=0;i<G[U].size();++i){
if(!used[G[U][i].v]){
dfs(G[U][i].v);
}
}
tv.push_back(U);
}
void rdfs(int U,int K){
used[U]=1;
cmp[U]=K;
for(int i=0;i<rG[U].size();++i){
if(!used[rG[U][i]]){
rdfs(rG[U][i],K);
}
}
}
int scc(){
memset(used,0,sizeof(used));
tv.clear();
for(int i=1;i<=n;++i){
if(!used[i]){
dfs(i);
}
}
memset(used,0,sizeof(used));
int K=0;
for(int i=tv.size()-1;i>=0;--i){
if(!used[tv[i]]){
rdfs(tv[i],++K);
}
}
return K;
}
int main(){
int x,y,z;
scanf("%d%d",&n,&m);
for(int i=1;i<=m;++i){
scanf("%d%d%d",&us[i],&vs[i],&ws[i]);
AddEdge(vs[i],us[i],ws[i]);
}
int sccs=scc();
for(int i=1;i<=m;++i){
if(cmp[vs[i]]==cmp[us[i]] && ws[i]>0){
puts("-1");
return 0;
}
}
for(int i=1;i<=n;++i){
G[i].clear();
}
for(int i=1;i<=m;++i){
if(cmp[vs[i]]!=cmp[us[i]]){
++ru[cmp[us[i]]];
G[cmp[vs[i]]].push_back((Edge){cmp[us[i]],ws[i]});
}
}
queue<int>q;
for(int i=1;i<=sccs;++i){
if(!ru[i]){
q.push(i);
}
}
while(!q.empty()){
int U=q.front(); q.pop();
for(int i=0;i<G[U].size();++i){
f[G[U][i].v]=max(f[G[U][i].v],f[U]+G[U][i].w);
--ru[G[U][i].v];
if(!ru[G[U][i].v]){
q.push(G[U][i].v);
}
}
}
if(*max_element(f+1,f+sccs+1)>100){
puts("-1");
return 0;
}
for(int i=1;i<=n;++i){
ansa[i]=f[cmp[i]];
}
for(int i=1;i<=n;++i){
G[i].clear();
rG[i].clear();
}
for(int i=1;i<=m;++i){
AddEdge(us[i],vs[i],-ws[i]);
}
sccs=scc();
for(int i=1;i<=m;++i){
if(cmp[us[i]]==cmp[vs[i]] && ws[i]<0){
puts("-1");
return 0;
}
}
for(int i=1;i<=n;++i){
G[i].clear();
}
for(int i=1;i<=m;++i){
if(cmp[us[i]]!=cmp[vs[i]]){
++ru[cmp[vs[i]]];
G[cmp[us[i]]].push_back((Edge){cmp[vs[i]],-ws[i]});
}
}
memset(f,0x7f,sizeof(f));
for(int i=1;i<=sccs;++i){
if(!ru[i]){
q.push(i);
f[i]=100;
}
}
while(!q.empty()){
int U=q.front(); q.pop();
for(int i=0;i<G[U].size();++i){
f[G[U][i].v]=min(f[G[U][i].v],f[U]+G[U][i].w);
--ru[G[U][i].v];
if(!ru[G[U][i].v]){
q.push(G[U][i].v);
}
}
}
if(*min_element(f+1,f+sccs+1)<0){
puts("-1");
return 0;
}
for(int i=1;i<=n;++i){
printf("%d %d\n",ansa[i],f[cmp[i]]);
}
return 0;
}
【差分约束系统】【强连通分量缩点】【拓扑排序】【DAG最短路】CDOJ1638 红藕香残玉簟秋，轻解罗裳，独上兰舟。