EOJ B. 杨柳依依

题目链接

B. 杨柳依依

题目分析

第一眼看到这一题就觉得挺简单的（虽然我没有做出来 ），一个一个扫点标记，最后再统计就好了，然后正解也差不多
但是本人码力实在是不足，然后写出以下代码

#include 
#include 
#include 
#include 
#include 
#define ll long long 
using namespace std;const int maxn = 80050 ;
int n,m,a,b,k,l;
int cnt,h[maxn],vis[5050],dis[5050],ans=-1;inline int readint()
{int x = 0 , f = 1 ; char c = getchar() ;while ( c > '9' || c < '0' ) { if ( c == '-' ) f = -1 ; c = getchar() ; }while ( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; } return f * x ;
}struct node
{int next , to , val ;
}edg[maxn] ;void add (int u , int v ,int val)
{++cnt ;edg[cnt].next = h[u] ;edg[cnt].to = v ;edg[cnt].val = val ;h[u] = cnt ;
}void dfs ( int u )
{for ( int i = h[u] ; i ; i = edg[i].next ){int v = edg[i].to ;if ( !vis[v] ){vis[v] = 1 ;++dis[v] ;//printf ("%d %d\n",v,dis[v]) ;if ( v == b ) {	l = 1 ; return ;} dfs( v ) ;if ( l == 1 ) return ;vis[v] = 0 ;--dis[v] ;}}
}int main()
{n = readint() , m = readint() ;for ( int i = 1 ; i <= m ; ++i ){int u = readint() , v = readint() ;add ( u , v , 1 ) ; add ( v , u , 1 ) ;}k = readint() ;for ( int i = 1 ; i <= k ; ++i ){memset(vis,0,sizeof(vis)) ;a = readint() , b = readint() ;vis[a] = 1 ; ++dis[a]; dfs( a ) ;}for ( int i = 0 ; i < n ; ++i ){if ( dis[i] > dis[ans] )ans = i ;//printf("%d ",dis[i]);}printf("%d\n",ans) ;
}

其实我只会dfs ，题目要求中也有要用double，咱也不明白哪里要用，然后水了9分，还过了挺多点，我就是菜啦（震声） 。
最后附上不知名正解代码

#include 
#include 
#include 
#include 
#include 
using namespace std;inline int read()
{int x = 0 , f = 1 ; char c = getchar() ;while ( c > '9' || c < '0' ) { if ( c == '-' ) f = -1 ; c = getchar() ; }while ( c >= '0' && c <= '9' ) { x = x * 10 + c - '0' ; c = getchar() ; } return f * x ;
}const int N=5e3+10,M=4e4+10;struct Edge
{int to , next ;
} edg[M<<1] ;struct Node 
{int pos,dis;Node ( int _pos=0,int _dis=0 ) : pos(_pos),dis(_dis) {}bool operator < ( const Node &t2 ) const { return dis>t2.dis; }
};priority_queue<Node> q;
queue<int> que;
int n,m,k,h[N],dis[N],res[N],cnt;
double ans[N],maxx=-0x3f;
bool vis[N];void add( int u , int v )
{++cnt ;edg[cnt].to = v ;edg[cnt].next = h[u] ;h[u] = cnt ;
}void SPFA( int S , int T )//最短路 
{memset( dis,63,sizeof(dis) ) ;dis[S] = 0; res[S] = 1;	q.push( Node(S,0) ) ;while ( !q.empty() ){int u = q.top().pos ; q.pop() ;for ( int i = h[u] ; i ; i = edg[i].next ){int v = edg[i].to;if ( dis[v] > dis[u] + 1 ){dis[v] = dis[u] + 1 ; res[v] = res[u] ;q.push(Node(v,dis[v]));	}	else if ( dis[v] == dis[u] + 1 ) res[v] += res[u];}	} 
}void bfs( int S , int T )
{memset( vis,0,sizeof(vis) );que.push(T) ; vis[T] = 1 ;ans[S] += 1.0 ; while ( !que.empty() ){int u = que.front() ; que.pop() ;ans[u] += res[u] * 1.0 / res[T] ;//计算概率 for ( int i = h[u] ; i ; i = edg[i].next ){int v = edg[i].to ;if ( dis[u] == dis[v] + 1 )if ( !vis[v] && (v ^ S) )que.push(v) , vis[v] = 1 ;}}
}int main()
{n = read() ; m = read() ;for ( int i = 1 , u , v ; i <=m ; i++ )u = read() , v = read() , add(u , v) , add(v , u) ;k = read() ;for ( int i = 1, a , b ; i<=k ; i++ ){a = read() ; b = read() ;SPFA( a , b ) ; bfs( a , b ) ;}int pos = 0 ;for ( int i = 1 ; i <=n ; i++ )if ( ans[i] > maxx )maxx = ans[i] , pos = i ;printf( "%d\n",pos ) ;//选取经过最多节点 return 0;
}

总结与反思

1. 对学过的知识没有熟练的掌握
2. 码力不足，想出的东西无法用代码实现
3. 要学会使用数据结构

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！