4TLE,比较抽象,看了几个贴都没有发现错误
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int INF = 0x3f3f3f3f;
namespace FOLW
{
struct edge
{
int to,nxt,w,c;
}e[maxn << 1];
int head[maxn],tot;
void add_edge(int u,int v,int w,int c)
{
e[++tot].nxt = head[u];
head[u] = tot;
e[tot].to = v;
e[tot].w = w;
e[tot].c = c;
}
void add(int u,int v,int w,int c)
{
add_edge(u,v,w,c);
add_edge(v,u,0,-c);
}
int dis[maxn],now[maxn];
bool vis[maxn];
bool spfa(int s,int t)
{
memset(dis,63,sizeof(dis));
memcpy(now,head,sizeof(head));
queue<int> q;
q.push(s);
dis[s] = 0;
vis[s] = 1;
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u] = 0;
for(int i = head[u];i;i = e[i].nxt)
{
int v = e[i].to;
if(e[i].w && dis[v] > dis[u] + e[i].c)
{
dis[v] = dis[u] + e[i].c;
if(!vis[v])
{
q.push(v);
vis[v] = 1;
}
}
}
}
return dis[t] != INF;
}
int ret;
int dfs(int u,int t,int flow)
{
if(u == t)return flow;
vis[u] = 1;
int ans = 0;
for(int i = now[u];i;i = e[i].nxt)
{
int v = e[i].to;
if(!vis[v] && e[i].w && dis[v] == dis[u] + e[i].c)
{
int x = dfs(v,t,min(e[i].w,flow - ans));
if(x)ret += x * e[i].c,e[i].w -= x,e[i ^ 1].w += x,ans += x;
}
}
vis[u] = 0;
return ans;
}
int dinic(int s,int t)
{
int ans = 0,flow = 0;
while(spfa(s,t))
{
while(flow = dfs(s,t,INF))ans += flow;
}
return ans;
}
}using namespace FOLW;
int n,m,s,t;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin >> n >> m >> s >> t;
while(m--)
{
int u,v,w,c;
cin >> u >> v >> w >> c;
add(u,v,w,c);
}
int ans = dinic(s,t);
cout << ans << " " << ret << '\n';
return 0;
}