最近在刷图论专题，这道题难度还算可以，顺便复习了一下差分约束。
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;
}
文章浏览阅读130次。题意：求重复次数最多的连续重复子串的长度题解：其实上一篇已经写过这种题【POJ-3693】了，只不过那题最后是要求解最后的串，这题只需要求出循环次数即可。一样的思路，枚举重复长度为L，就有rk[pos]rk[pos]rk[pos]和rk[pos+L]rk[pos+L]rk[pos+L]这两个串，pos为枚举的L的倍数，即rk[k∗L]rk[k*L]rk[k∗L]和rk[(k+1)∗L)]r..._spoj_687
文章浏览阅读3.4k次。PlantFlagTool¶OverviewThis tutorial shows how to write a new tool for RViz.In RViz, a tool is a class that determines how mouse events interact with the visualizer. In this example we descri_plant flag
文章浏览阅读1.9k次。应用安全设计规范的一个甲方模板，对新老系统的安全设计按照应用安全级别提供了一个管理规范
文章浏览阅读2.2k次。MT2503平台技术资料介绍：包括原理图、参考设计、规格书、源码、FAQ等一系列技术资料，有需要的可到一牛网论坛中下载或者到小编的CSDN资源里下载。此外，还有MT2503平台方案开发，MT2503模块等需要合作的，到一牛网论坛或在下方留言都可以。MT2503_all_feature__GPIO_Mapping_v1_0.rarMT2503_Ballmap_Package_V0.2.zi..._mt2503和mt2601
文章浏览阅读910次。写在最前Docker安装RocketMQRocketMQ 入门必读Spring Boot 整合 RocketMQDemo 地址：mingyue-springboot-rocketmq1.添加依赖<dependency> <groupId>org.apache.rocketmq</groupId> <artifactId>rocketmq-spring-boot-starter</artifactId> <_springboot rocketmq队列发送1000条数据抢
文章浏览阅读1.8k次。以哪吒之魔童降世影片的海报为例进行图片爬取参考网址：哪吒之魔童降世官方海报爬虫逻辑：【分页网页url采集】-【数据采集】-【保存图片】经过前两篇文章的实践，可以发现两种爬虫逻辑各有优缺点，逻辑（一）可以获得相对详细的信息，但是需要从主url中获取分页url再进行数据的爬取，很消耗时间，而逻辑（二）则是直接获取在第一个url上的信息，爬取即可，很省时，当然相对地获取的信息也就较少一些。而这次..._python 爬取电影海报
文章浏览阅读52次。哈勃空间望远镜显示草帽星系正在经历一次合并事件和狂野西部的亡命之徒一样，草帽星系盘面的辽阔边缘可能隐藏了动荡的过去。草帽星系(梅西叶星表编号为M104)从不是适合某个模型的星系。有个有趣发现，它是盘面旋涡星系和足球那样的椭圆星系的混合体。草帽星系的结构演变历程变得愈发奇怪，因为来自哈勃太空望远镜新证据表示草帽星系是一次重大星系合并的结果，虽然它光滑的盘面没有迹象表明有重大混乱等。这个星系微弱的晕圈...
文章浏览阅读280次。idea提示忽略大小写File -> Settings -> Editor -> General -> Code Completion 在最上面的“Match case”默认是选中的，取消勾选idea在提示的时候就忽略大小写了，最后记得点apply或者OK如有疑问或其他问题，可以进QQ群咨询 ：920199935..._idea代码补全提示忽略大小写 2022
文章浏览阅读264次。1.关于setC++ STL 之所以得到广泛的赞誉，也被很多人使用，不只是提供了像vector, string, list等方便的容器，更重要的是STL封装了许多复杂的数据结构算法和大量常用数据结构操作。vector封装数组，list封装了链表，map和set封装了二叉树等，在封装这些数据结构的时候，STL按照程序员的使用习惯，以成员函数方式提供的常用操作，如：插入、排序、删除、查找等。让_c++ 插入方便访问方便的容器
文章浏览阅读499次。转自：iOS各种调试技巧豪华套餐目录 前言逼优鸡知己知彼 百战不殆抽刀断Bug 普通操作 全局断点（Global BreakPoint） 条件断点(Condational Breakpoints)打印的艺术 NSLog 开启僵尸对象(Enable NSZombie Objects)进击的码农 Console(_viewdebug 类型强转输出ios
文章浏览阅读522次，点赞25次，收藏30次。小编精心为大家准备了一手资料以上Java高级架构资料、源码、笔记、视频。Dubbo、Redis、设计模式、Netty、zookeeper、Spring cloud、分布式、高并发等架构技术【附】架构书籍BAT面试的20道高频数据库问题解析Java面试宝典Netty实战算法BATJ面试要点及Java架构师进阶资料《互联网大厂面试真题解析、进阶开发核心学习笔记、全套讲解视频、实战项目源码讲义》点击传送门即可获取！[外链图片转存中…(img-WlkN4aWP-1712599790854)]
文章浏览阅读855次。1.Win + r 打开运行窗口，输入 regedit.exe2.依次找到如下路径：HKEY_LOCAL_MACHINE\Software\Microsoft\windows\CurrentVersion\Explorer如果文件夹下没有Max Cached Icons这个选项，也就是右侧没有Max Cached Icons这个选项，就新建一个Max Cached Icons这个选项，数值数据为20003.上面的路径下面再往下找到ShellIconOverlayIdentifiers文件夹.._git 取消文件夹绿色