[COCI2011-2012#7]|[COCI2011-2012#7] KAMPANJA
这个题似曾相识啊，以前是用搜索剪枝+0/1边权bfs做的(题面可以参照上一篇这个题的博客)。
有一类问题就是求 包含若干关键点的最小强联通子图大小是多少。
如果关键点数量是变量，那么就是NP问题了。。。
对于本题来说，关键点数量=2，就可以直接dp啦。
【[COCI2011-2012#7]|[COCI2011-2012#7] KAMPANJA】设一个走正向边的点p和一个走逆向边的点q，f[i][j] 即是 p在i且q在j最少经过的点数，转移的话把去的路径伸直然后在纸上画一画，发现总共有三种：
1.i向后扩展一个点
2.j向后扩展一个点
3.i,j通过i到j的最短路径互换位置。
因为状态图并不是dag，所以跑个dij就可以了。
#include
#define ll long long
using namespace std;
const int N=205;
#define pb push_backint n,m,f[N][N],ans,to[N*2];
int ne[N*2],hd[N],num,d[N][N];
bool v[N][N];
struct node{
int x,y;
bool operator <(const node &u)const{
return f[x][y]>f[u.x][u.y];
}
};
priority_queue q;
inline void add(int x,int y){ to[++num]=y,ne[num]=hd[x],hd[x]=num;
}inline void solve(){
for(int i=1;
i<=n;
i++) d[i][i]=0;
for(int k=1;
k<=n;
k++)
for(int i=1;
i<=n;
i++)
for(int j=1;
j<=n;
j++) if(d[i][k]+d[k][j] 转载于:https://www.cnblogs.com/JYYHH/p/9179571.html
推荐阅读
- 猎杀IP
- 开花店的前景怎么样（）
- 滚这个字
- 一个懂得和他自己灵魂沟通的人，这个人一定是正直善良的人
- 残卷
- 炉火温暖
- 在这个时代每个女性都应该用个性的服装来证明自己的存在
- 躺着中枪
- 没有导入future这个module
- 一劳永逸地解决词汇量不够的问题