最开始的代码:
#include<bits/stdc++.h>
#define pk push_back
#define mk make_pair
#define int long long
using namespace std;
typedef long long LL;
typedef pair<int,int> pi;
const int N=105,M=105*10,inf=0x3f3f3f3f;
int n,m,ans,a[N],b[N],cc[N],f[N],_head[N];
int tot=1,to[M],nxt[M],w[M],c[M],head[N],de[N];
void add(int x,int y,int z,int g){
to[++tot]=y,w[tot]=z,c[tot]=g,nxt[tot]=head[x],head[x]=tot;
to[++tot]=x,w[tot]=0,c[tot]=-g,nxt[tot]=head[y],head[y]=tot;
}
int d[N],vis[N],du[N];
bool spfa(int s,int t){
memset(d,0x3f,sizeof d);
//for(int i=s;i<=t;++i) d[i]=inf; 修改后
queue<int> q;vis[s]=1;d[s]=0;q.push(s);
while(!q.empty()){
int x=q.front();q.pop();vis[x]=0;
for(int i=head[x];i;i=nxt[i]){
if(d[x]+c[i]>=d[to[i]]||!w[i]) continue;
d[to[i]]=d[x]+c[i];
if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=1;
}
}
return d[t]^inf;
}
int dinic(int x,int t,int flow){
if(x==t) return flow;
int rest=flow;
vis[x]=1;
for(int i=head[x];i&&rest;i=nxt[i]){
if(vis[to[i]]||d[x]+c[i]!=d[to[i]]||!w[i]) continue;
int k=dinic(to[i],t,min(w[i],flow));
if(!k) d[to[i]]=0;
w[i]-=k;
w[i^1]+=k;
rest-=k;
ans+=k*c[i];
}
vis[x]=0;
return flow-rest;
}
signed main(){
ios::sync_with_stdio(false);
cin>>n>>m;
for(int i=1;i<=m;++i){
cin>>a[i]>>b[i]>>cc[i]>>f[i];
if(f[i]<=cc[i]) add(b[i],a[i],f[i],1),add(a[i],b[i],cc[i]-f[i],1);
else{
ans+=f[i]-cc[i];
add(b[i],a[i],cc[i],1),add(b[i],a[i],f[i]-cc[i],0);
}
add(a[i],b[i],inf,2);
de[a[i]]-=f[i],de[b[i]]+=f[i];
}
int s=0,t=n+1;
for(int i=1;i<=n;++i)if(de[i]>0) add(s,i,de[i],0);else if(de[i]<0) add(i,t,-de[i],0);
add(n,1,inf,0);
while(spfa(s,t)) dinic(s,t,inf);
cout<<ans<<endl;
return 0;
}
TLE #27
我想着是不是没开longlong的原因呢,把关于流量跟花费的变量换成了longlong,然后TLE #26。
我又把spfa()里数组d的初始化改成手动的,然后TLE #31。
人傻常数大?SOS