康康代码QwQ
by Qiuly @ 2019-03-22 20:49:13
@[樱初音斗橡皮](/space/show?uid=66287)
by Qiuly @ 2019-03-22 20:49:18
这个超时很不正常，每个点均超过了1200ms
by Qiuly @ 2019-03-22 20:49:53
@[Qiuly](/space/show?uid=113190)
'''
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
int n, m, s, t;
namespace header
{
const int N=400002;
int head[N];
struct node
{
int to, nxt, wei, cst;
} edge[N];
int cnt=1;
void add_edge(int f, int t, int w, int c)
{
cnt++;
edge[cnt].to=t;
edge[cnt].nxt=head[f];
edge[cnt].wei=w;
edge[cnt].cst=c;
head[f]=cnt;
return;
}
int dist[N];
bool vis[N];
bool spfa()
{
std::memset(dist, 0x3f, sizeof(dist));
std::memset(vis, 0x00, sizeof(vis));
std::queue<int> q;
q.push(s), dist[s]=0, vis[s]=true;
while (!q.empty())
{
int f=q.front();
q.pop();
vis[f]=false;
for (int i=head[f]; i!=-1; i=edge[i].nxt)
{
if (!edge[i].wei)
continue;
int to=edge[i].to;
if (dist[to]>dist[f]+edge[i].wei*edge[i].cst)
{
dist[to]=dist[f]+edge[i].wei*edge[i].cst;
if (!vis[to])
q.push(to), vis[to]=true;
}
}
}
return dist[t]!=0x3f3f3f3f;
}
int maxflow=0, mincost=0;
int dfs(int i, int minf)
{
//printf("in dfs(%d, %d)\n", i, minf);
if (i==t)
{
maxflow+=minf;
//printf("out of dfs, return %d\n", minf);
return minf;
}
int u=0;
for (int j=head[i]; j!=-1; j=edge[j].nxt)
{
int to=edge[j].to;
if (edge[j].wei&&dist[to]==dist[i]+edge[i].wei*edge[i].cst)
{
int f=dfs(to, std::min(minf-u, edge[j].wei));
mincost+=edge[i].cst*f;
u+=f;
edge[j].wei-=f;
edge[j^1].wei+=f;
if (minf==u)
break;
}
}
//printf("out of dfs, return %d\n", u);
return u;
}
}
using namespace header;
int main()
{
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i=1; i<=n; ++i)
head[i]=-1;
for (int i=1; i<=m; ++i)
{
int x, y, w, f;
scanf("%d%d%d%d", &x, &y, &w, &f);
add_edge(x, y, w, f);
add_edge(y, x, 0, -f);
}
while (spfa())
dfs(s, 0x3f3f3f3f);
printf("%d %d\n", maxflow, mincost);
return 0;
}
'''
by 樱初音斗橡皮 @ 2019-03-22 20:52:01
@[Qiuly](/space/show?uid=113190) gosh我不会markdown，现在在手机上又没有插入代码的键
by 樱初音斗橡皮 @ 2019-03-22 20:52:49
要不我把我的AC板子发出来？？QvQ
by Qiuly @ 2019-03-22 20:53:26
｀｀｀
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
int n, m, s, t;
namespace header
{
const int N=400002;
int head[N];
struct node
{
int to, nxt, wei, cst;
} edge[N];
int cnt=1;
void add_edge(int f, int t, int w, int c)
{
cnt++;
edge[cnt].to=t;
edge[cnt].nxt=head[f];
edge[cnt].wei=w;
edge[cnt].cst=c;
head[f]=cnt;
return;
}
int dist[N];
bool vis[N];
bool spfa()
{
std::memset(dist, 0x3f, sizeof(dist));
std::memset(vis, 0x00, sizeof(vis));
std::queue<int> q;
q.push(s), dist[s]=0, vis[s]=true;
while (!q.empty())
{
int f=q.front();
q.pop();
vis[f]=false;
for (int i=head[f]; i!=-1; i=edge[i].nxt)
{
if (!edge[i].wei)
continue;
int to=edge[i].to;
if (dist[to]>dist[f]+edge[i].wei*edge[i].cst)
{
dist[to]=dist[f]+edge[i].wei*edge[i].cst;
if (!vis[to])
q.push(to), vis[to]=true;
}
}
}
return dist[t]!=0x3f3f3f3f;
}
int maxflow=0, mincost=0;
int dfs(int i, int minf)
{
//printf("in dfs(%d, %d)\n", i, minf);
if (i==t)
{
maxflow+=minf;
//printf("out of dfs, return %d\n", minf);
return minf;
}
int u=0;
for (int j=head[i]; j!=-1; j=edge[j].nxt)
{
int to=edge[j].to;
if (edge[j].wei&&dist[to]==dist[i]+edge[i].wei*edge[i].cst)
{
int f=dfs(to, std::min(minf-u, edge[j].wei));
mincost+=edge[i].cst*f;
u+=f;
edge[j].wei-=f;
edge[j^1].wei+=f;
if (minf==u)
break;
}
}
//printf("out of dfs, return %d\n", u);
return u;
}
}
using namespace header;
int main()
{
scanf("%d%d%d%d", &n, &m, &s, &t);
for (int i=1; i<=n; ++i)
head[i]=-1;
for (int i=1; i<=m; ++i)
{
int x, y, w, f;
scanf("%d%d%d%d", &x, &y, &w, &f);
add_edge(x, y, w, f);
add_edge(y, x, 0, -f);
}
while (spfa())
dfs(s, 0x3f3f3f3f);
printf("%d %d\n", maxflow, mincost);
return 0;
}
｀｀｀
by 樱初音斗橡皮 @ 2019-03-22 20:53:39
哦发现提交记录没了......
by Qiuly @ 2019-03-22 20:53:44
。。。不会用手机洛谷
by 樱初音斗橡皮 @ 2019-03-22 20:53:56
```cpp
```
by Qiuly @ 2019-03-22 20:54:38