问题描述
小ww开了一家快递公司，在nn个城市之间进行货物运输工作，一共雇了mm个快递员。 每个快递员性格很奇特，第ii号快递员只愿意将货物从城市sisi运送到titi（甚至不愿意将货物 从titi运送到sisi），并且如果他运送的货物量x≤dix≤di，那么他要求获得的报酬为x×aix×ai，否则为 di×ai+(x−di)×bidi×ai+(x−di)×bi。
现在小ww 接到一个大订单，需要将ff单位货物从ss 运送到tt，请求出小ww 的最小开支。 你可以假定每个快递员的运货量没有限制。
输入格式
第一行五个整数nn，mm，ss，tt，ff。
接下来mm行每行五个数sisi，titi，aiai，bibi，didi，描述一个快递员的信息。
输出格式
如有解请输出最小小开支，否则请输出Impossible。
输入样例
4 4 0 3 5
0 1 3 0 3
1 3 3 0 3
0 2 2 1 6
2 3 2 1 6输出样例
18数据范围
n≤100,m≤1000n≤100,m≤1000
si,ti,s,t≤n−1si,ti,s,t≤n−1
f,di≤200f,di≤200
ai,bi≤1000ai,bi≤1000.
保证至多只有一名邮递员ai<biai<bi,其余均是ai>biai>bi。
共5050组数据，保证数据有梯度。
题目分析
交了7发，终于AC了，满满的都是泪。
看完题目打了个SPFA上去，76分，我会把这个代码贴出来的。
然后会被卡掉，会出现负权边的情况，惊悚。还有只有一个环，我就不怂了，于是我开始不停的交代码。我们找出来那个负边，很明显ai<bi,导致最好是运送较少的次数。我们用floyd暴力跑出来即可。这道题有点卡常数，可能会写崩。
代码实现
76分SPFA不判负环
#include<bits/stdc++.h>
using namespace std;
#define RE register long long
#define IL inline
#define N 101
#define M 1001
#define int long long
#define inf 21474983647
IL char gc(){
static char buf[],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}template<class T>IL int read(T&x){
x=;register char c=gc();
while(c<)c=gc();
while(c>)x=(x<<)+(x<<)+(c^),c=gc();
}void write(RE x){
if (x>)write(x/);
putchar(x%^);
}int m,n,s,t,f,head[N],dis[N],cnt;
bitset<N>vis;
queue<int>q;
struct aa{int next,v,a,b,d;}e[M];
IL void addedge(RE u,RE v,RE a,RE b,RE d){e[++cnt]=(aa){head[u],v,a,b,d},head[u]=cnt;}
IL int work(RE i,RE x){return x<=e[i].d?x*e[i].a:e[i].d*e[i].a+(x-e[i].d)*e[i].b;}
IL int SPFA(RE u){memset(dis,0x3f,sizeof dis);
q.push(u),dis[u]=;
while (q.size()){
RE u=q.front();
q.pop(),vis[u]=;
for (RE v,i=head[u];i;i=e[i].next)
if (dis[v=e[i].v]>dis[u]+work(i,f)){
dis[v=e[i].v]=dis[u]+work(i,f);
if (!vis[v]) q.push(v),vis[v]=;
}
}return dis[t];
}signed main(){
read(n),read(m),read(s),read(t),read(f),++s,++t;
for (RE i=,s1,t,a,b,d;i^m;++i) read(s1),read(t),read(a),read(b),read(d),++s1,++t,addedge(s1,t,a,b,d);
RE ans=SPFA(s);
if (ans==inf)puts("Impoosble");
else write(ans);
}
100分代码
#include<bits/stdc++.h>
using namespace std;
#define RE register long long
#define IL inline
#define N 101
#define M 10001
#define int long long
#define inf 4557430888798830399
IL char gc(){
static char buf[],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,,,stdin),p1==p2)?EOF:*p1++;
}template<class T>IL int read(T&x){
x=;RE f=;
register char c=gc();
while(c<)f|=c=='-',c=gc();
while(c>)x=(x<<)+(x<<)+(c^),c=gc();
if (f) x=-x;
}void write(RE x){if (x>) write(x/);
putchar(x%^);
}int ans,fi,m,n,s,t,f,cnt1,cnt2,head1[N],head2[N],dis1[N],dis2[N],d1[N][N],d2[N][N];
struct aa{int next,v,a,b,d;}e1[M],e2[M];
bitset<N>vis;
queue<int>q;IL void addedge1(RE u,RE v,RE a,RE b,RE d){
e1[++cnt1]=(aa){head1[u],v,a,b,d},head1[u]=cnt1;
}IL void addedge2(RE s,RE t,RE a,RE b,RE d){e2[++cnt2]=(aa){head2[s],t,a,b,d},head2[s]=cnt2;}
IL int work(int i,int x){return x<=e1[i].d?x*e1[i].a:e1[i].d*e1[i].a+(x-e1[i].d)*e1[i].b;}
IL int spfa1(RE u){q.push(u),dis1[u]=;
while(q.size()){
RE u=q.front();q.pop(),vis[u]=;
for (RE i=head1[u],v;i;i=e1[i].next)
if (dis1[v=e1[i].v]>dis1[u]+work(i,f)){
dis1[v]=dis1[u]+work(i,f);
if (!vis[v]) q.push(v),vis[v]=;
}
}return dis1[t];
}IL int spfa2(RE u){q.push(u),dis2[u]=;
while(q.size()){
RE u=q.front();q.pop(),vis[u]=;
for (RE v,i=head2[u];i;i=e2[i].next)
if (dis2[v=e2[i].v]>dis2[u]+work(i,f)){
dis2[v]=dis2[u]+work(i,f);
if (!vis[v]) q.push(v),vis[v]=;
}
}return dis2[s];
}void floyd(){
for (RE i=;i<=n;++i)
for (RE v,j=head1[i];j;j=e1[j].next)
d1[i][v=e1[j].v]=min(d1[i][v],work(j,e1[fi].d));
for (RE k=;k<=n;++k) for (RE i=;i<=n;++i)
for (RE j=;j<=n;++j) d1[i][j]=min(d1[i][j],d1[i][k]+d1[k][j]);
for (RE i=;i<=n;++i)
for (RE v,j=head1[i];j;j=e1[j].next)
if (j^fi) d2[i][v=e1[j].v]=min(d2[i][v],work(j,f-e1[fi].d));
for (RE k=;k<=n;++k) for (RE i=;i<=n;++i)
for (RE j=;j<=n;++j) d2[i][j]=min(d2[i][j],d2[i][k]+d2[k][j]);
}signed main(){
//freopen("transport.in","r",stdin),freopen("transport.out","w",stdout);
read(n),read(m),read(s),read(t),read(f),++s,++t;
for (RE s1,t1,a,b,d,i=;i<=m;++i){
read(s1),read(t1),read(a),read(b),read(d);
++s1,++t1;if (a<b) fi=i;
addedge1(s1,t1,a,b,d),addedge2(t1,s1,a,b,d);
}memset(dis1,0x3f,sizeof dis1),memset(dis2,0x3f,sizeof dis2);
memset(d1,0x3f,sizeof d1),memset(d2,0x3f,sizeof d2);
ans=spfa1(s);
if (fi&&e1[fi].d<f){
spfa2(t),floyd();
for (RE i=;i<=n;++i)
for (RE j=;j<=n;++j)
if (i^j&&dis1[i]^inf&&d1[i][j]^inf&&d2[i][j]^inf&&dis2[j]^inf)
ans=min(ans,dis1[i]+d1[i][j]+d2[i][j]+dis2[j]);
}if (ans==inf) puts("Impossible");
else cout<<ans;
}
代码说明
SPFA比较裸，跳过，注意下标要加一，神坑。我们在判断负环的时候，需要用两种情况来判断，我们先用暴力储存d1。然后用反向边再次跑一遍floyd存在d2，然后我们加起来就可以了。做负环题，就是要把环拆开变成两条边，就可以了。
最后我扯一点别的东西，请听下回分解。