[COCI2011-2012#7] KAMPANJA

这个题似曾相识啊，以前是用搜索剪枝+0/1边权bfs做的(题面可以参照上一篇这个题的博客)。

有一类问题就是求包含若干关键点的最小强联通子图大小是多少。

如果关键点数量是变量，那么就是NP问题了。。。

对于本题来说，关键点数量=2，就可以直接dp啦。

设一个走正向边的点p和一个走逆向边的点q，f[i][j] 即是 p在i且q在j最少经过的点数，转移的话把去的路径伸直然后在纸上画一画，发现总共有三种：

1.i向后扩展一个点

2.j向后扩展一个点

3.i,j通过i到j的最短路径互换位置。

因为状态图并不是dag，所以跑个dij就可以了。

#include<bits/stdc++.h>

#define ll long long

using namespace std;

const int N=205;

#define pb push_back

int 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<node> 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]<d[i][j]) d[i][j]=d[i][k]+d[k][j];

	f[1][1]=1; node x;

	q.push((node){1,1});

	while(!q.empty()){

		x=q.top(),q.pop();

//		cout<<x.x<<' '<<x.y<<' '<<f[x.x][x.y]<<endl;

        if(v[x.x][x.y]) continue;

        v[x.x][x.y]=1;

		if(x.x!=x.y&&f[x.x][x.y]+d[x.x][x.y]<=f[x.y][x.x]){

			f[x.y][x.x]=f[x.x][x.y]+d[x.x][x.y]-1;

			q.push((node){x.y,x.x});

		}

		for(int i=hd[x.x];i;i=ne[i]) if((i&1)&&f[x.x][x.y]+(to[i]!=x.y)<f[to[i]][x.y]){

			f[to[i]][x.y]=f[x.x][x.y]+(to[i]!=x.y);

			q.push((node){to[i],x.y});

		}	

		for(int i=hd[x.y];i;i=ne[i]) if(!(i&1)&&f[x.x][x.y]+(to[i]!=x.x)<f[x.x][to[i]]){

			f[x.x][to[i]]=f[x.x][x.y]+(to[i]!=x.x);

			q.push((node){x.x,to[i]});

		}

	}

	ans=f[2][2]?f[2][2]:-1;

}

int main(){

//	freopen("data.in","r",stdin);

//	freopen("data.out","w",stdout);

	memset(d,0x3f,sizeof(d));

	memset(f,0x3f,sizeof(f));

	scanf("%d%d",&n,&m);

	int uu,vv;

	for(int i=1;i<=m;i++){

		scanf("%d%d",&uu,&vv);

		add(uu,vv),add(vv,uu);

		d[uu][vv]=1;

	}

	solve();

	printf("%d\n",ans);

	return 0;

}

巴特西

[COCI2011-2012#7] KAMPANJA

最新文章

热门文章