uva搬题

la 3523

找奇圈,找到点双后判断二分图,染色

la 4287

求强联通分量,然后找出度入度为0的点分别为$$a,b$$ $$ans=max(a,b)$$
特殊情况整个图本来就是强连通的,那么$$ans=0$$;
证明:我们考虑一个图,如果他被证明的话
那么他至少有一个入度和出度,我们再发现,加一条边
相当于 $$a++ b++$$
所以答案就是$$max a,b$$

uva 11324

求强联通分量,然后在生成的dag上跑最长路
注意:生成的一定是$$dag$$(scc的定义)

uva11374

跑两遍最短路,然后枚举每一条边,更新答案
idea:

可以求最短路的条数
设d[i]表示到汇点的最短路
我们可以证明一个性质,最短路上面的所有点,在整个图中,
相互之间都是最短路(表达的不太好)
于是我们设$$f[i]$$表示$$ i$$到汇点的最短路
于是就有方程$$f[i]=sum{f[j]|d[i]=d[j]+w(i,j)}$$
ps:可以用类似的方法求出次短路的条数
可惜我次短路都不会求。。

uva 11090

spfa判断一下负环,0/1分数规划 二分 裸题

发表评论

电子邮件地址不会被公开。 必填项已用*标注