最近在刷图论专题，这道题难度还算可以，顺便复习了一下差分约束。
1、建边
第一种可变形为 -1<=Xa-Xb<=-1 第二种变形为Xc-Xd<=0，根据差分约束，对于第一种，由Xa向Xb建权值为1的边，由Xb向Xa建权值为-1的边。
对于第二种，由Xc向Xd建权值为0的边。
2、tarjan缩点
由第一种构建出来的会出现环，依据差分约束系统，这些强连通分量内部的答案显然是最长路+1，所以tarjan统计出每个强连通分量
3、floyd求最长路
第二种会把这些强连通分量连接起来，所以只需分别求出每个强连通分量的最长路+1，再求sigma。
4、floyd判正环
只需初始化w[i][i]=0,跑完最长路之后看w[i][i]是否仍为0即可。
#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<cstring>
#define inf -10000000
using namespace std;
struct bian
{
int qi,zhong,w,next;
};
bian c[400010];
int n,m1,m2,jishu=0,jishu1=0,ans=0,jishu2=0,jishu3=0,w[610][610];
int dfn[610],low[610],belong[610],head[610],zhan[610];
bool in[610];
int x,y;
void add(int x,int y,int z)
{
c[++jishu].qi=x;
c[jishu].zhong=y;
c[jishu].w=z;
c[jishu].next=head[x];
head[x]=jishu;
}
void tarjan(int x)
{
dfn[x]=++jishu2;
low[x]=jishu2;
zhan[++jishu3]=x;
in[x]=1;
for(int i=head[x];i;i=c[i].next)
{
if(dfn[c[i].zhong]==-1)
{
tarjan(c[i].zhong);
low[x]=min(low[x],low[c[i].zhong]);
}
else if(in[c[i].zhong])
low[x]=min(low[x],dfn[c[i].zhong]);
}
if(low[x]==dfn[x])
{
int y;
jishu1++;
while(1)
{
y=zhan[jishu3--];
in[y]=0;
belong[y]=jishu1;
if(x==y)
break;
}
}
}
int main()
{
cin>>n>>m1>>m2;
memset(dfn,-1,sizeof(dfn));
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
w[i][j]=inf;
for(int i=1;i<=n;++i)
w[i][i]=0;
for(int i=1;i<=m1;++i)
{
cin>>x>>y;
add(x,y,1);
add(y,x,-1);
w[x][y]=max(w[x][y],1);
w[y][x]=max(w[y][x],-1);
}
for(int i=1;i<=m2;++i)
{
cin>>x>>y;
add(x,y,0);
w[x][y]=max(w[x][y],0);
}
for(int i=1;i<=n;++i)
if(dfn[i]==-1)
tarjan(i);
for(int i=1;i<=jishu1;++i)
{
int da=inf;
for(int k=1;k<=n;++k)
{
if(belong[k]!=i) continue;
for(int j=1;j<=n;++j)
{
if(belong[j]!=i||w[j][k]==inf) continue;
for(int l=1;l<=n;++l)
{
if(belong[l]!=i||w[k][l]==inf) continue;
if(w[j][l]<w[j][k]+w[k][l])
w[j][l]=w[j][k]+w[k][l];
}
}
}
for(int j=1;j<=n;++j)
{
if(belong[j]!=i) continue;
for(int k=1;k<=n;++k)
{
if(belong[k]!=i||w[j][k]==inf) continue;
da=max(da,abs(w[j][k]));
}
}
ans+=da+1;
}
for(int i=1;i<=n;++i)
if(w[i][i])
{
cout<<"NIE";
return 0;
}
cout<<ans;
return 0;
}
文章浏览阅读1.4k次。根据钱江晚报官方微博的报导，最新的肥胖计算方法为：体重(kg) / 身高(m) 的平方。如果超过 25，你就是胖子。于是本题就请你编写程序自动判断一个人到底算不算胖子。输入格式：输入在一行中给出两个正数，依次为一个人的体重（以 kg 为单位）和身高（以 m 为单位），其间以空格分隔。其中体重不超过 1000 kg，身高不超过 3.0 m。输出格式：首先输出将该人的体重和身高代入肥胖...
文章浏览阅读598次。Python中 list, numpy.array, torch.Tensor 格式相互转化原地址：https://www.cnblogs.com/siyuan1998/p/10792481.html1.1 list 转 numpyndarray = np.array(list)1.2 numpy 转 listlist = ndarray.tolist()2.1 list 转 torch.Tensortensor=torch.Tensor(list)2.2 torch.Tensor 转 li_一个列表中含多个torch.tensor如何转化为np.array
文章浏览阅读4.9k次。【操作过程】：（1）根据项目描述要求在/home/guestuser1/目录下分别创建work1和work2两个子目录，由于已经明确所要生成目录的绝对路径，所以可以通过mkdir命令直接生成指定的目录，执行命令：$mkdir /home/guestuser1/work1$mkdir /home/guestuser1/work2需要注意的是，在生成目录时，可以使用绝对路径，也可以使用相对路径。如果只写出一个目录的名字，则新的目录将会在当前目录中。（2）要进入指定的路径，可以直接使用_(1)创建目录/home/guestuser1/work1,/home/guestuser/work2;(2)将当前目录切
文章浏览阅读652次。一、注解模式@Component注解默认实例化的对象是单例，如果想声明成多例对象可以使用@Scope(“prototype”)@Repository默认单例@Service默认单例@Controller默认多例二、Spring中的bean的生命周期singleton（全局的）是随着spring的存亡而存亡prototype 又叫多例模式，用的时候就new一下，用完就没有了。session 存在这一次会话 session 中，session过期后它就没了。request_spring用注解设置bean的生命周期注解是那个
文章浏览阅读7.3k次，点赞12次，收藏73次。垃圾分类是将来生活可持续发展的必需项。但是很多人由于缺乏垃圾分类知识，或是因为垃圾分类困难，费时费力，所以没有好好贯彻垃圾分类政策，此时设计一款方便于群众进行智能化垃圾识别分类的微信小程序就显得尤为必要。_垃圾分类微信小程序
文章浏览阅读831次。Loader在Android3.0引进，它让异步加载数据变得容易。特征：1.在Activity、Fragment中都可以使用2.Loader可以提供异步加载数据3.监视数据源的变化，当数据源发生变化的时候，会传递新的数据4.当loader重建的时候，会自动链接到最后一个Loader的cursor数据上，而不去进行重新查找。在app中使用Loader的时候，可能使_onloaderapk
文章浏览阅读2.1w次，点赞18次，收藏19次。问题出现环境：ubuntu16.04 ,anacona中的一个py37的环境，pip版本20.0.1当时是为了install fbs，使用conda环境python对应的pip报错如下：ImportError: cannot import name 'PackageFinder' from 'pip._internal.index' (/home/yushan/anaconda3/lib/..._importerror: cannot import name 'packagefinder' from 'pip._internal.index' (
文章浏览阅读159次。Python 算法与数据结构视频教程课程简介数据结构和算法是每个程序员需要掌握的基础知识之一，也是面试中跨不过的槛。目前关于 Python 算法和数据结构的中文资料比较欠缺，笔者尝试录制视频教程帮助 Python 初学者掌握常用算法和数据结构，提升开发技能。本教程是付费教程(文字内容和代码免费)，因为笔者录制的过程中除了购买软件、手写板等硬件之外，业余需要花费很多时间和精力来录制视频、查资料、编写..._算法导论作者 开发数学编辑器
文章浏览阅读2.2k次。1.问题现象工作电脑系统为ubuntu16.04，昨天早上使用时，突然发现多出来一个100Mb的盘符，类似新增了一个硬盘，进入后可以看到ubuntu系统的各个目录结构及相关文件，但是并不wan'zhe_ubuntu重启后配置都没有了
文章浏览阅读1k次，点赞21次，收藏14次。程序建立了多主体综合能源模型，采用双层模型进行求解，上层用自适应粒子群算法求解出各能源售价和需求响应补偿价格；下层采用混合整数规划算法求解出三个园区、配电网、储能电站、集中型风电场间的最优调度策略。
文章浏览阅读1.9w次，点赞13次，收藏45次。最近有使用Matlab通过mex调用CUDA加速视频处理的需求，于是折腾了一下，网上的说法可谓千奇百怪众说纷纭，却没有能用的。经过六个多小时的反复搜索和尝试，本人终于成功编译运动了了matlab的mexCUDA例程：mexGPUExample.cu。1.软件环境这个过程涉及三个环境：Visual Studio、Cuda Toolkit和Matlab。其中Cuda依赖Visual Studio、Mat_mexcuda
文章浏览阅读1.8k次。删除ackplugin插件、卸载ackplugin插件、卸载ack、如何卸载电脑上ackplugin 登录插件、ackplugin卸载时需要密码怎么办请用密码:123456，试试.我的卸载密码就是这个...._ackplugin