第一眼感觉终于看到了一道自己会做的题,不就是最小割裸题嘛简单。然后,发现正解是传说中的最小割转最短路。。
比较玄学。
//Twenty#include#include #include #include #include #include #include #include using namespace std;const int maxn=1000+299;const int N=2*1000*1000+29;int s,t,n,m,hl[maxn][maxn],sl[maxn][maxn],xl[maxn][maxn],tot;int fir[N],nxt[N*4],to[N*4],val[N*4],ecnt,vis[N],dis[N],ans,mi1=1e9,mi2=1e9;void add(int u,int v,int w) { nxt[++ecnt]=fir[u]; fir[u]=ecnt; to[ecnt]=v; val[ecnt]=w; nxt[++ecnt]=fir[v]; fir[v]=ecnt; to[ecnt]=u; val[ecnt]=w;}queue que;void spfa() { while(!que.empty()) que.pop(); memset(vis,0,sizeof(vis)); memset(dis,127,sizeof(dis)); dis[s]=0; vis[s]=1; que.push(s); while(!que.empty()) { int now=que.front(); que.pop(); vis[now]=0; for(int i=fir[now];i;i=nxt[i]) { if(dis[to[i]]>dis[now]+val[i]) { dis[to[i]]=dis[now]+val[i]; if(!vis[to[i]]) { vis[to[i]]=1; que.push(to[i]); } } } }}int main() { //freopen(".in","r",stdin); //freopen(".out","w",stdout); while(scanf("%d%d",&n,&m)==2){ ecnt=0; memset(fir,0,sizeof(fir)); for(int i=1;i<=n;i++) for(int j=1;j