kIG7Z8oP @ 2019-02-10 19:30:24
//第二个点R了
//dinic算法
//bfs分层并判断是否连通
//d[]表示深度,c容量f流量,rev反边
//cur:当前弧优化
#include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
const int MAXN=10010;
struct Edge
{
int from,to,cap,flow,rev;
Edge(){}
Edge(int _from,int _to,int _cap,int _flow,int _rev): from(_from),to(_to),cap(_cap),flow(_flow),rev(_rev){};
};
vector<Edge> g[MAXN];
int cur[MAXN],s,t;
void insert(int u,int v,int c)//u->v,容量c
{
g[u].push_back(Edge(u,v,c,0,g[v].size()));
g[v].push_back(Edge(v,u,0,0,g[u].size()-1));
}
int d[MAXN];
struct queue
{
int val[MAXN],head,tail;
void push(int k){val[tail]=k;tail++;}
int top(){return val[head];}
void pop(){head++;}
bool empty(){return head==tail;}
queue(){}
};
queue q;
int bfs()//找层,并判断是否是联通的
{
memset(d,0,sizeof(d));
q.push(s);
d[s]=1;
while(!q.empty())
{
int now=q.top();
q.pop();
for(int i=0;i<g[now].size();i++)
{
Edge e=g[now][i];
if(!d[e.to]&&e.cap>e.flow) d[e.to]=d[now]+1,q.push(e.to);
}
}
return d[t];
}
int dfs(int now,int a)//available
{
if(now==t||!a) return a;
int flow=0;
for(int &i=cur[now];i<g[now].size();i++)//记住这段话
{
Edge &e=g[now][i];
if(d[e.to]==d[now]+1&&e.cap>e.flow)
{
int f=dfs(e.to,min(a,e.cap-e.flow));
a-=f,flow+=f,e.flow+=f,g[e.to][e.rev].flow-=f;
}
if(!a) break;
}
if(a) d[now]=-1;
return flow;
}
int n,m;
int main()
{
int fr,too,c;
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&fr,&too,&c);
insert(fr,too,c);
}
int res=0;
while(bfs())
{
memset(cur,0,sizeof(cur));
res+=dfs(s,2147483647);
}
printf("%d",res);
}
by Resux @ 2019-02-10 20:19:41
这是哪一题?
by Catalan1906 @ 2019-02-10 20:42:37
@kIG7Z8oP
不知道诶……你把queue改成手写的试试,如果实在不行开long long?(不过这道题似乎不用long long)
by Catalan1906 @ 2019-02-10 20:46:50
@kIG7Z8oP 如果还是找不到错就把vector改成前向星吧……
by Catalan1906 @ 2019-02-10 20:47:22
@kIG7Z8oP 刚刚看错了……你的queue似乎就是手写的,把它改成stl试试
by kIG7Z8oP @ 2019-02-10 21:22:26
@Neptune_Disaster QAQ
by Catalan1906 @ 2019-02-10 21:23:57
@kIG7Z8oP 我没写过当前弧优化……你用正常的Dinic或许能过呢qwq
by kIG7Z8oP @ 2019-02-11 08:07:49
@Neptune_Disaster 锅出在bfs上
by revolIA @ 2019-03-04 17:33:22
我来告诉你,很简单,你把maxn改成1e5就可以了,估计是出题人数据范围没写好,我也re过