萌新初学oi,求助网络流, 由于不会spfa,就用了dij算法,照着题解打(模板题应该没问题吧),但过不去样例
#include<bits/stdc++.h>
using namespace std;
const long long inf=0x7fffffffffffffff;
inline int read(){
char c;
int ret=0;
for(c=getchar();c<'0'||c>'9';c=getchar());
for(;c>='0'&&c<='9';c=getchar())ret=ret*10+c-'0';
return ret;
}
inline void write(int x) {
if(x<0) putchar('-'),x=-x;
if(x>9) write(x/10);
putchar(x%10+'0');
}
class line{
public:
long long u,v,w,c;
line *next;
line(int u=0,int v=0,int w=0,int c=0,line *next=NULL):
u(u),v(v),w(w),c(c),next(next){}
}*L[5009];
class node{
public:
line *edge;
void newline(int u,int v,int w,int c){edge=new line(u,v,w,c,edge);}
}dat[5009];
long long n,m,s,t,u,v,w,c,mincost,maxflow,dis[5009],flow[5009],from[5009],last,h[5009];
bool vis[5009];
bool dij(long long start,long long end){
line *p;
long long minn,mn;
last=start;
for(int i=1;i<=n;i++){
dis[i]=inf;
flow[i]=inf;
from[i]=vis[i]=0;
L[i]=NULL;
}
dis[start]=0;
vis[start]=true;
flow[start]=inf;
for(p=dat[last].edge;p!=NULL;p=p->next){
if(p->w>0&&vis[p->v]==false&&dis[p->v]>dis[last]+p->w+h[last]-h[p->v]){
dis[p->v]=dis[last]+p->c+h[last]-h[p->v];
flow[p->v]=min(p->w,flow[last]);
from[p->v]=last;
L[p->v]=p;
}
}
for(int i=2;i<=n;i++){
minn=inf;
mn=-1;
for(int i=1;i<=n;i++)
if(vis[i]==false&&minn>dis[i]){
minn=dis[i];mn=i;
}
if(mn==-1)return false;
vis[mn]=true;
if(mn==end)return true;
for(p=dat[last].edge;p!=NULL;p=p->next){
if(p->w>0&&vis[p->v]==false&&dis[p->v]>dis[last]+p->w+h[last]-h[p->v]){
dis[p->v]=dis[last]+p->c+h[last]-h[p->v];
flow[p->v]=min(p->w,flow[last]);
from[p->v]=last;
L[p->v]=p;
}
}
last=mn;
}
return dis[end]!=inf;
}
line *get(line *p){
for(line*q=dat[p->v].edge;q!=NULL;q=q->next)if(q->v==p->u)return q;
return NULL;
}
int main(){
freopen("read.txt","r",stdin);
n=read();m=read();s=read();t=read();
for(int i=1;i<=m;i++){
u=read();v=read();w=read();c=read();
dat[u].newline(u,v,w,c);dat[v].newline(v,u,0,-c);
}
while(dij(s,t)){
mincost+=flow[t]*(dis[t]-h[s]+h[t]);
maxflow+=flow[t];
for(int i=t;i!=s;i=from[i]){
L[i]->w-=flow[t];
get(L[i])->w+=flow[t];
}
for(int i=1;i<=n;i++)
if(dis[i]!=inf)h[i]+=dis[i];
}
write(mincost);putchar(' ');write(maxflow);
}
样例输出:
60 20