残酷月光 @ 2019-08-07 09:24:13
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
#define Max 10005
#define inf 0x3f3f3f3f
#define max(a,b) a>b?a:b;
#define min(a,b) a>b?b:a;
using namespace std;
queue<int> q;
int n,m,x,y,w,st,end;
int g[Max][Max]; //目前还剩的容量
int pre[Max];//保存增广路径
int flow[Max]; //源点到目前点的最大流量
int max_flow;//ans
void init()
{
max_flow=0;
memset(flow,0,sizeof(flow));
memset(g,0,sizeof(g));
}
inline int bfs(int st,int end)
{
while(q.size()) q.pop();
for(int i=1;i<=n;i++) //点初始化
pre[i]=-1;
pre[st]=0;
q.push(st);
flow[st]=inf;
int temp;
while(q.size())
{
temp=q.front();
q.pop();
if(temp==end) break;//到汇点了
for(int i=1;i<=n;i++)
{
if(g[temp][i]>0&&pre[i]==-1)
{
pre[i]=temp;
flow[i]=min(flow[temp],g[temp][i]); //维护最小值
q.push(i);
}
}
}
if(pre[end]==-1)
return -1;
else
return flow[end];
}
void EK(int st,int end)
{
int increase=0; //每次增加的流量
int last;
while((increase=bfs(st,end))!=-1)
{
int k=end;
while(k!=st) //搜索已经找到的增广路劲
{
last=pre[k];
g[last][k]-=increase; //正向减少
g[k][last]+=increase; //反向增加
k=last;
}
max_flow+=increase;
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&st,&end);
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&w);
g[x][y]+=w;
}
EK(st,end);
printf("%d\n",max_flow);
return 0;
}
奇怪的是还有70分。难道是队列炸了??还是没过.....
by 残酷月光 @ 2019-08-07 09:26:00
而且炸的数据,本地能跑出来。。。。
by installb @ 2019-08-07 09:28:04
int g[Max][Max];
明显开不下这么大啊
这题不能邻接矩阵存图
by 残酷月光 @ 2019-08-07 09:31:50
@installb 但是还有70分,这让我很怀疑。,我本来觉得应该会超时,毕竟每次遍历全部,但是居然有70分,有点奇怪。。
by 童年如作业 @ 2019-08-07 09:43:47
@残酷月光 这我试过
by 童年如作业 @ 2019-08-07 09:46:03
还有这是模板,估计是为了大家的代码无论写多丑、不卡常,思想对都能跑出AC,数据肯定不会特别卡(不然你让Dinic怎么活)
by 残酷月光 @ 2019-08-07 09:52:35
@童年如作业 Dinic一般不是比EK更快嘛?一个O(VE^2) 一个O(V^2E)
显然边大于点
by 童年如作业 @ 2019-08-07 10:01:21
@残酷月光 我知道啊,我说的是模板可能并不在时间上卡算法
by 童年如作业 @ 2019-08-07 10:02:03
(当然你打超级无敌大暴力就当我没说)
by Magallan_forever @ 2019-09-28 16:58:30
@童年如作业 【模板】快速排序