图论|[BZOJ1894][COCI2011-2012第7场]总统演讲图论|最短路

题目描述临近选举，总统要在城市1和城市2举行演讲。他乘汽车完成巡回演讲，从1出发，途中要经过城市2，最后必须回到城市1.特勤局对总统要经过的所有城市监控。为了使得费用最小，必须使得监控的城市最少。求最少要监控的城市。一共有N个城市，有M条有向边。(0<=N,M<=200)。有N从1出发途中要经过2，最后要回到1的路线中最少要经过的点的数目。

输入第一行包含2个整数N,M。N表示城市的数目，M表示有向边的数目。接下来m行，每行两个数A,B，表示从A到B有一条有向边。

输出：最少要访问的城市的数量。

样例输入

6 7

1 3

3 4

4 5

5 1

4 2

2 6 6 3
5 8
1 3
5 2
3 4
2 4
4 3
4 2
3 1
1 5

样例输出 6
4
题解：做两次DFS，第一次求出1至2的最少点数，第二次求出2至1的最少点数

#include #include #include #include #include #include using namespace std; const int INF=0x3f3f3f3f; const int N=205; int n, m, ans, sum, fir[N]; struct node{ int e, next; }edge[N]; bool vis1[N], vis2[N]; void Link( int s, int e, int i ) { edge[i].e=e; edge[i].next=fir[s]; fir[s]=i; } void DFS2( int r ) { if( sum>=ans ) return; if( r==1 ) { ans=sum; return; } vis2[r]=1; if( !vis1[r] ) sum++; //vis1记录过的点可以重复走, 但不能重复累加 for( int i=fir[r]; i; i=edge[i].next ) if( !vis2[edge[i].e] ) DFS2( edge[i].e ); vis2[r]=0; if( !vis1[r] ) sum--; } void DFS1( int r) { if( sum>=ans ) return; if( r==2 ) { DFS2( r ); return; } vis1[r]=1; sum++; for( int i=fir[r]; i; i=edge[i].next ) if( !vis1[edge[i].e] ) DFS1( edge[i].e ); //不能重复走 vis1[r]=0; sum--; } int main() { scanf( "%d%d", &n, &m ); for( int i=1; i<=m; i++ ) { int s, e; scanf( "%d%d", &s, &e ); Link( s, e, i ); } ans=INF; DFS1( 1 ); printf( "%d\n", ans ); return 0; }