求解！
/*
查看题目 Show Problem
题目:网络运输货物
问题编号:481 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]
My Flag:Unaccepted
题目类型
网络流
描述
有一条公路，点1是仓库所在地（物资的起点），n是某一工地（物资的终点）每条弧旁的两个数字分别表示某一时间内通过该段路的最多吨数和每吨物资通过该段路的费用。
输入格式
第一行：1个数N(0<n<100)
从第2行~+00行 是a到b 能通过c吨 每吨价值为d。
(0<a,b<100)
输出格式
1个数：通过最多货物使用的最小钱。
样例输入
5
1 2 10 4
1 3 8 1
2 4 2 6
2 5 7 1
3 2 5 2
3 4 10 3
4 5 4 2
0 0 0 0
样例输出
55
*/
#define MAX 10000000
#define MAXN 100
#define MAXE 10000
#include<iostream>
using namespace std；
struct edge
{
int from；
int to；
int cost；
int capacity；
int next；
} edges[MAXE+1]；
int hLink[MAXN+1],index=0,n；
void insert(int from,int to,int cost,int capacity){
index++；
edges[index].from=from；
edges[index].to=to；
edges[index].cost=cost；
edges[index].capacity=capacity；
edges[index].next=hLink[from]；
hLink[from]=index；
}
int dis[MAXN+1]；
int que[MAXE],nxt[MAXN+1],front,rear；
bool inque[MAXN+1]；
bool spfa(){
for (int i=1；i<=n；++i){
inque[i]=false；
dis[i]=MAX；
}
dis[1]=0；
front=rear=0；
inque[1]=true；
que[rear++]=1；
nxt[1]=0；
while (front<rear){
int present=que[front++]；
front%=MAXE；
inque[present]=false；
for (int i=hLink[present]；i；){
if (edges[i].capacity==0){
i=edges[i].next；
continue；
}
if (dis[edges[i].to]>dis[present]+edges[i].cost){
dis[edges[i].to]=dis[present]+edges[i].cost；
nxt[edges[i].to]=i；
if (!inque[edges[i].to]){
inque[edges[i].to]=true；
que[rear++]=edges[i].to；
rear%=MAXE；
}
}
i=edges[i].next；
}
}
return dis[n]!=MAX；
}
int ans=0；
void maxflow(){
int MinCap=MAX；
for (int i=nxt[n]；i；i=nxt[edges[i].from])
if (MinCap>edges[i].capacity)
MinCap=edges[i].capacity；
for (int i=nxt[n]；i；i=nxt[edges[i].from]){
edges[i].capacity-=MinCap；
ans+=MinCap*edges[i].cost；
}
}
int mincostmaxflow(){
while (spfa()) maxflow()；
return ans；
}
int main (void){
cin>>n；
for (int i=1；i<=n；++i)
hLink[i]=0；
int a,b,c,d；
cin>>a>>b>>c>>d；
while (a!=0||b!=0||c!=0||d!=0){
insert(a,b,c,d)；
cin>>a>>b>>c>>d；
}
cout<<mincostmaxflow()；
while (1)；
return 0；
}
状态题目:网络运输货物
题目编号:481-网络运输货物 查看该题
状态: Unaccepted
测评机： Xeost[5]
得分： 10分
提交日期： 2009-7-4 23:10:00
有效耗时： 47毫秒
测试结果1: 测试结果错误.错误结果为:49
正确结果应为:55
测试结果2: 通过本测试点|有效耗时47ms
测试结果3: 测试结果错误.错误结果为:169
正确结果应为:107
测试结果4: 测试结果错误.错误结果为:2257
正确结果应为:3640
测试结果5: 测试结果错误.错误结果为:4749
正确结果应为:5386
测试结果6: 测试结果错误.错误结果为:12054
正确结果应为:22612
测试结果7: 测试结果错误.错误结果为:35032
正确结果应为:11386
测试结果8: 测试结果错误.错误结果为:13584
正确结果应为:13490
测试结果9: 测试结果错误.错误结果为:34797
正确结果应为:25883
测试结果10: 测试结果错误.错误结果为:24436
正确结果应为:28273
提交代码： /*
查看题目 Show Problem
题目:网络运输货物
问题编号:481 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]
My Flag:Unaccepted
题目类型
网络流
描述
有一条公路，点1是仓库所在地（物资的起点），n是某一工地（物资的终点）每条弧旁的两个数字分别表示某一时间内通过该段路的最多吨数和每吨物资通过该段路的费用。
输入格式
第一行：1个数N(0<n<100)
从第2行~+00行 是a到b 能通过c吨 每吨价值为d。
(0<a,b<100)
输出格式
1个数：通过最多货物使用的最小钱。
样例输入
5
1 2 10 4
1 3 8 1
2 4 2 6
2 5 7 1
3 2 5 2
3 4 10 3
4 5 4 2
0 0 0 0
样例输出
55
*/
#define MAX 10000000
#define MAXN 100
#define MAXE 10000
#include<iostream>
using namespace std；
struct edge
{
int from；
int to；
int cost；
int capacity；
int next；
} edges[MAXE+1]；
int hLink[MAXN+1],index=0,n；
void insert(int from,int to,int cost,int capacity){
index++；
edges[index].from=from；
edges[index].to=to；
edges[index].cost=cost；
edges[index].capacity=capacity；
edges[index].next=hLink[from]；
hLink[from]=index；
}
int dis[MAXN+1]；
int que[MAXE],nxt[MAXN+1],front,rear；
bool inque[MAXN+1]；
bool spfa(){
for (int i=1；i<=n；++i){
inque[i]=false；
dis[i]=MAX；
}
dis[1]=0；
front=rear=0；
inque[1]=true；
que[rear++]=1；
nxt[1]=0；
while (front<rear){
int present=que[front++]；
front%=MAXE；
inque[present]=false；
for (int i=hLink[present]；i；){
if (edges[i].capacity==0){
i=edges[i].next；
continue；
}
if (dis[edges[i].to]>dis[present]+edges[i].cost){
dis[edges[i].to]=dis[present]+edges[i].cost；
nxt[edges[i].to]=i；
if (!inque[edges[i].to]){
inque[edges[i].to]=true；
que[rear++]=edges[i].to；
rear%=MAXE；
}
}
i=edges[i].next；
}
}
return dis[n]!=MAX；
}
int ans=0；
void maxflow(){
int MinCap=MAX；
for (int i=nxt[n]；i；i=nxt[edges[i].from])
if (MinCap>edges[i].capacity)
MinCap=edges[i].capacity；
for (int i=nxt[n]；i；i=nxt[edges[i].from]){
edges[i].capacity-=MinCap；
ans+=MinCap*edges[i].cost；
}
}
int mincostmaxflow(){
while (spfa()) maxflow()；
return ans；
}
int main (void){
cin>>n；
for (int i=1；i<=n；++i)
hLink[i]=0；
int a,b,c,d；
cin>>a>>b>>c>>d；
while (a!=0||b!=0||c!=0||d!=0){
insert(a,b,c,d)；
cin>>a>>b>>c>>d；
}
cout<<mincostmaxflow()；
// while (1)；
return 0；
}
-------------------------------------------
查看状态 Show Status
状态题目:网络运输货物
题目编号:481-网络运输货物 查看该题
状态: Unaccepted
测评机： Xeost[5]
得分： 60分
提交日期： 2009-7-5 19:51:00
有效耗时： 313毫秒
测试结果1: 测试结果错误.错误结果为:60
正确结果应为:55
测试结果2: 通过本测试点|有效耗时47ms
测试结果3: 测试结果错误.错误结果为:184
正确结果应为:107
测试结果4: 通过本测试点|有效耗时63ms
测试结果5: 通过本测试点|有效耗时47ms
测试结果6: 通过本测试点|有效耗时63ms
测试结果7: 测试结果错误.错误结果为:12739
正确结果应为:11386
测试结果8: 通过本测试点|有效耗时47ms
测试结果9: 通过本测试点|有效耗时46ms
测试结果10: 测试结果错误.错误结果为:37481
正确结果应为:28273
提交代码： /*
查看题目 Show Problem
题目:网络运输货物
问题编号:481 [提交该题] [讨论该问题] [有关讨论] [Who AC] [相关题解] [最优解]
My Flag:Unaccepted
题目类型
网络流
描述
有一条公路，点1是仓库所在地（物资的起点），n是某一工地（物资的终点）每条弧旁的两个数字分别表示某一时间内通过该段路的最多吨数和每吨物资通过该段路的费用。
输入格式
第一行：1个数N(0<n<100)
从第2行~+00行 是a到b 能通过c吨 每吨价值为d。
(0<a,b<100)
输出格式
1个数：通过最多货物使用的最小钱。
样例输入
5
1 2 10 4
1 3 8 1
2 4 2 6
2 5 7 1
3 2 5 2
3 4 10 3
4 5 4 2
0 0 0 0
样例输出
55
*/
#define MAX 10000000
#define MAXN 100
#define MAXE 10000
#include<iostream>
using namespace std；
struct edge
{
int from；
int to；
int cost；
int capacity；
int next；
} edges[MAXE+1]；
int hLink[MAXN+1],index=0,n；
void insert(int from,int to,int cost,int capacity){
index++；
edges[index].from=from；
edges[index].to=to；
edges[index].cost=cost；
edges[index].capacity=capacity；
edges[index].next=hLink[from]；
hLink[from]=index；
}
int dis[MAXN+1]；
int que[MAXE],nxt[MAXN+1],front,rear；
bool inque[MAXN+1]；
bool spfa(){
for (int i=1；i<=n；++i){
inque[i]=false；
dis[i]=MAX；
}
dis[1]=0；
front=rear=0；
inque[1]=true；
que[rear++]=1；
nxt[1]=0；
while (front<rear){
int present=que[front++]；
front%=MAXE；
inque[present]=false；
for (int i=hLink[present]；i；){
if (edges[i].capacity==0){
i=edges[i].next；
continue；
}
if (dis[edges[i].to]>dis[present]+edges[i].cost){
dis[edges[i].to]=dis[present]+edges[i].cost；
nxt[edges[i].to]=i；
if (!inque[edges[i].to]){
inque[edges[i].to]=true；
que[rear++]=edges[i].to；
rear%=MAXE；
}
}
i=edges[i].next；
}
}
return dis[n]!=MAX；
}
int ans=0；
void maxflow(){
int MinCap=MAX；
for (int i=nxt[n]；i；i=nxt[edges[i].from])
if (MinCap>edges[i].capacity)
MinCap=edges[i].capacity；
for (int i=nxt[n]；i；i=nxt[edges[i].from]){
edges[i].capacity-=MinCap；
ans+=MinCap*edges[i].cost；
}
}
int mincostmaxflow(){
while (spfa()) maxflow()；
return ans；
}
int main (void){
cin>>n；
for (int i=1；i<=n；++i)
hLink[i]=0；
int a,b,c,d；
cin>>a>>b>>d>>c；
while (a!=0||b!=0||c!=0||d!=0){
insert(a,b,c,d)；
cin>>a>>b>>d>>c；
}
cout<<mincostmaxflow()；
// while (1)；
return 0；
}