之前的Dinic模板照着刘汝佳写的vector然后十分鬼畜跑得奇慢无比,虽然别人这样写也没慢多少但是自己的就是令人捉急。
改成邻接表之后快了三倍,虽然还是比较慢但是自己比较满意了。虽然一开始ecnt从0开始WA了一发。。。
之前的码风也十分鬼畜呀缩进只缩1、2格不懂自己怎么想的。。
反正今天就安心划划水。
#include#include #include #include #include #include #include typedef long long LL;const int maxn=20050,maxm=200050,INF=0x7f7f7f7f;using namespace std;int n,m,s,t,u,v,w,ecnt=1,fir[maxn],dis[maxn],cur[maxn],ans;struct edge { int from,to,cap,flow,nxt; edge(){} edge(int from,int to,int cap,int flow,int nxt):from(from),to(to),cap(cap),flow(flow),nxt(nxt){}}e[maxm];void add(int u,int v,int w) { e[++ecnt]=edge(u,v,w,0,fir[u]); e[++ecnt]=edge(v,u,0,0,fir[v]); fir[u]=ecnt-1; fir[v]=ecnt;}void init() { scanf("%d%d%d%d",&n,&m,&s,&t); for(int i=1;i<=m;i++) { scanf("%d%d%d",&u,&v,&w); add(u,v,w); }}queue que;int bfs(int s,int t) { memset(dis,0,sizeof(dis)); dis[s]=1; que.push(s); while(!que.empty()) { int x=que.front() ;que.pop(); for(int i=fir[x];i;i=e[i].nxt) if(!dis[e[i].to]&&e[i].flow