不是常数问题,下了数据,一个马上过一个根本跑不出来。
//TLE
#include<bits/stdc++.h>
#define au arc[u]
using namespace std;
const int N = 5e3 + 5, M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int s,t,n, m,u,v, tot = 1, last[N], arc[N], to[M], back[M], w[M], c[M], dist[N], cg;
bool in[N];
queue<int>q;
void link(int u,int v,int weight,int cost){
to[++tot]=v,w[tot]=weight,c[tot]=cost;
back[tot]=last[u],last[u]=tot;
}
bool spfa(){
memcpy(arc,last,sizeof last),
memset(dist,0x3f,sizeof dist);
for(q.push(s),in[s]=true,dist[s]=0;!q.empty();q.pop(),in[u]=false){
for(int i=last[u=q.front()];i;i=back[i]){
if(w[i]&&dist[v=to[i]]>dist[u]+c[i]){
dist[v]=dist[u]+c[i];
if(!in[v])q.push(v),in[v]=true;
}
}
}
return dist[t]!=1061109567;
}
int dfs(int u,int maxi) {
if (u == t) return maxi;
int sum=0,flow;in[u]=true;
for (; arc[u]; arc[u] = back[arc[u]]) {
v = to[arc[u]];
if (!in[v] && dist[v] == dist[u] + c[arc[u]]) {
flow= dfs(v,std::min(w[arc[u]], maxi - sum));
cg += flow* c[arc[u]], w[arc[u]] -= flow, w[arc[u] ^ 1] += flow, sum += flow;
if(sum>=maxi)break;
}
}
in[u]=false;
return sum;
}
int main() {
int w,c;
for(scanf("%d%d%d%d",&n,&m,&s,&t);m--;)
scanf("%d%d%d%d", &u, &v, &w, &c),
link(u, v, w, c),link(v,u,0,-c);
int ans = 0;
while (spfa())
for(int flow;(flow = dfs(s, INF));) ans += flow;
printf("%d %d\n", ans, cg);
return 0;
}
//AC
#include<bits/stdc++.h>
#define au arc[u]
using namespace std;
const int N = 5e3 + 5, M = 1e5 + 5;
const int INF = 0x3f3f3f3f;
int s,t,n, m,u,v, tot = 1, last[N], arc[N], to[M], back[M], w[M], c[M], dist[N], cg;
bool in[N];
queue<int>q;
void link(int u,int v,int weight,int cost){
to[++tot]=v,w[tot]=weight,c[tot]=cost;
back[tot]=last[u],last[u]=tot;
}
bool spfa(){
memcpy(arc,last,sizeof last),
memset(dist,0x3f,sizeof dist);
for(q.push(s),in[s]=true,dist[s]=0;!q.empty();q.pop(),in[u]=false){
for(int i=last[u=q.front()];i;i=back[i]){
if(w[i]&&dist[v=to[i]]>dist[u]+c[i]){
dist[v]=dist[u]+c[i];
if(!in[v])q.push(v),in[v]=true;
}
}
}
return dist[t]!=1061109567;
}
int dfs(int u,int maxi) {
if (u == t) return maxi;
int sum=0,flow;in[u]=true;
for (; arc[u]&&sum<maxi; arc[u] = back[arc[u]]) {
v = to[arc[u]];
if (!in[v] && dist[v] == dist[u] + c[arc[u]]) {
flow= dfs(v,std::min(w[arc[u]], maxi - sum));
cg += flow* c[arc[u]], w[arc[u]] -= flow, w[arc[u] ^ 1] += flow, sum += flow;
}
}
in[u]=false;
return sum;
}
int main() {
int w,c;
for(scanf("%d%d%d%d",&n,&m,&s,&t);m--;)
scanf("%d%d%d%d", &u, &v, &w, &c),
link(u, v, w, c),link(v,u,0,-c);
int ans = 0;
while (spfa())
for(int flow;(flow = dfs(s, INF));) ans += flow;
printf("%d %d\n", ans, cg);
return 0;
}
唯一区别就是dinic()把判断跳出的语句放出来了,不信的文件对比。