轩轩醉了 轩轩醉了
呐。。。
关注数: 58 粉丝数: 207 发帖数: 14,073 关注贴吧数: 8
蒟蒻初学网络流,求解最小费用最大流问题 如题,题目是rq481 题目描述 有一条公路,点1是仓库所在地(物资的起点),n是某一工地(物资的终点)每条弧旁的两个数字分别表示某一时间内通过该段路的最多吨数和每吨物资通过该段路的费用。 输入格式 第一行:1个数N(0<n<100) 从第2行~+00行 是a到b 能通过c吨 每吨价值为d。 (0<a,b<100) 输出格式 1个数:通过最多货物使用的最小钱。 测样例,我的输出总是比样例的大。。。 蒟蒻的代码如下,另有文件 #include <cstdio> #include <queue> #include <climits> #include <cstring> #include <cstdlib> #define MAXN 102 using namespace std; struct G{int c,f,F;}; G g[MAXN][MAXN]; int n,vs,vt,dist[MAXN],prev[MAXN]; bool vis[MAXN]; queue<int> q; void input(); bool spfa(); int argu(); int flow(); int main() { input(); printf("%d\n",flow()); return 0; } int flow() { int ans=0; while(spfa()) ans+=argu(); return ans; } int argu() { int min=INT_MAX,cost=0,e; for(int i=vt;i!=vs&&(e=abs(prev[i]));i=e) if(g[e][i].F-g[e][i].f<min) min=g[e][i].F-g[e][i].f; for(int i=vt;i!=vs;i=e) { e=prev[i]; g[e][i].f+=min; g[i][e].f-=min; cost+=g[e][i].c*min; } return cost; } bool spfa() { int u; for(int i=0;i<=n;dist[i++]=INT_MAX); memset(vis,0,sizeof(vis)); dist[vs]=0,prev[vs]=-1; q.push(vs); while(!q.empty()) { u=q.front(); q.pop(); for(int i=1;i<=n;++i) { if(g[u][i].F-g[u][i].f>0 && dist[u]+g[u][i].c<dist[i]) { dist[i]=dist[u]+g[u][i].c; prev[i]=u; if(!vis[i]) { q.push(i); vis[i]=true; } } } } return dist[vt]<INT_MAX; } void input() { int a,b,f,c; scanf("%d",&n); vs=1,vt=n; do{ scanf("%d%d%d%d",&a,&b,&f,&c); g[a].F=f; g[a].c=c; }while(a!=0||b!=0||c!=0||f!=0); }
首页 1 2 3 4 下一页