题意:有N个点,之间有P条路(双向),要求每次从1到N走不同的路T次,求这T次中两点间路最长的一条
思路:二分+最大流,如果两点之间有路,就建立流量为1的网络,然后二分路径长度,从新建立符合要求的图,求最大流
注意重边的情况,如果是邻接表没事,否则注意,边不是取最小,要都存下,因为有可能都符合要求,WA了很多次都是错在这了
三个小时就这么没了……今天一早,看出了原因了,于是用vector解决了,明显很慢啊,不知道是不是模板的原因……
核心code:
vector map[nMax][nMax]; //原始图 void rebuild(int mid) { memset(G, 0, sizeof(G)); memset(F, 0, sizeof(F)); //流 for(int i=1; i<=n; i++) for(int j=1; j<=n; j++) { int tt=map[i][j].size(); for(int t=0; t Min) { mid=(Max+Min)/2; rebuild(mid); //cout<<<" "; flow=find_max_flow(); if(flow>=t) Max=mid; else Min=mid+1; } printf("%d\n", Max); return 0; }