题面
个点,条双向边(正向与反向权值不同),求经过最大边权最小的欧拉回路的权值
分析
见 commonc大佬博客
- 精髓就是通过最大流调整无向边的方向使得所有点的入度等于出度
CODE
#include
#include
#include
using namespace std;
templateinline void read(T &num) {
char ch; while((ch=getchar())'9');
for(num=0;ch>='0'&&ch mid) return 0;
if(D[i] 0) add(i, T, deg[i]/2);
else if(deg[i] D[i]) swap(A[i], B[i]), swap(C[i], D[i]);
--deg[A[i]], ++deg[B[i]];
}
for(int i = 1; i > 1;
if(check(mid)) r = mid;
else l = mid+1;
}
printf("%dn", l);
}
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.e1idc.net