1834: [ZJOI2010]network 网络扩容
1834: [ZJOI2010]network 网络扩容
Time Limit: 3 Sec Memory Limit: 64 MBSubmit: 2309 Solved: 1157
[ Submit][ Status][ Discuss]
Description
给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。求： 1、 在不扩容的情况下，1到N的最大流； 2、 将1到N的最大流增加K所需的最小扩容费用。Input
输入文件的第一行包含三个整数N,M,K，表示有向图的点数、边数以及所需要增加的流量。 接下来的M行每行包含四个整数u,v,C,W，表示一条从u到v，容量为C，扩容费用为W的边。Output
输出文件一行包含两个整数，分别表示问题1和问题2的答案。Sample Input
5 8 21 2 5 8
2 5 9 9
5 1 6 2
5 1 1 8
1 2 8 7
2 5 4 9
1 2 1 1
1 4 2 1
Sample Output
13 1930%的数据中，N<=100
100%的数据中，N<=1000，M<=5000，K<=10
HINT
Source
Day1
日哦。。。。苟蒻改死掉发现是数组开太小？！！！！
打了dicnic发现还没有暴力算法来得快？！！！！
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;const int maxn = 1E3 + 10;struct E{int from,to,cap,flow,cost;
}G[20*maxn];int dis[maxn],fa[maxn],a[maxn],U[5*maxn],V[5*maxn],C[5*maxn],W[5*maxn],L[maxn],cnt[maxn];
int n,m,t,cur,flow,cost,mflow;
bool vis[maxn],flag = 1;vector v[maxn];
queue q;bool SPFA()
{for (int i = 1; i <= n; i++) dis[i] = ~0U>>1;memset(vis,0,sizeof(vis));dis[1] = 0; vis[1] = 1; a[1] = ~0U>>1; fa[1] = 0;q.push(1);while (!q.empty()) {int k = q.front(); q.pop(); vis[k] = 0;for (int i = 0; i < v[k].size(); i++) {E e = G[v[k][i]];if (e.cap > e.flow && dis[e.to] > dis[k] + e.cost) {dis[e.to] = dis[k] + e.cost;fa[e.to] = v[k][i];a[e.to] = min(a[k],e.cap - e.flow);if (!vis[e.to]) {vis[e.to] = 1;q.push(e.to);}}}}if (dis[n] == ~0U>>1) return 0;int A = a[n]; bool ret = 1;if (!flag && mflow - flow <= A) {A = mflow - flow; ret = 0;}flow += A; cost += dis[n]*A; int u = n; while (u != 1) {G[fa[u]].flow += A;G[fa[u]^1].flow -= A;u = G[fa[u]].from;} return ret;
}bool BFS()
{memset(L,0,sizeof(L));memset(cnt,0,sizeof(cnt));q.push(1);while (!q.empty()) {int k = q.front(); q.pop();for (int i = 0; i < v[k].size(); i++) {E e = G[v[k][i]];if (e.cap - e.flow && e.to != 1 && !L[e.to]) {L[e.to] = L[k] + 1;q.push(e.to);}}}return L[n];
}int DFS(int x,int a)
{if (x == n || a <= 0) return a;int ret = 0;for (int &i = cnt[x]; i < v[x].size(); i++) {E e = G[v[x][i]]; int f;if (L[e.to] == L[x] + 1 && (f = DFS(e.to,min(a,e.cap - e.flow))) > 0) {a -= f;G[v[x][i]].flow += f;G[v[x][i]^1].flow -= f;ret += f;if (!a) return ret;}}return ret;
}void Dicnic()
{while (BFS()) flow += DFS(1,~0U>>1);printf("%d ",flow);
}int main()
{#ifdef YZYfreopen("yzy.txt","r",stdin);#endifcin >> n >> m >> t;for (int i = 0; i < m; i++) {scanf("%d%d%d%d",&U[i],&V[i],&C[i],&W[i]);v[U[i]].push_back(cur); G[cur++] = (E){U[i],V[i],C[i],0,0};v[V[i]].push_back(cur); G[cur++] = (E){V[i],U[i],0,0,0};}//Dicnic(); while (SPFA()); flag = 0;printf("%d ",flow); mflow = flow + t;for (int i = 0; i < m; i++) {v[U[i]].push_back(cur); G[cur++] = (E){U[i],V[i],~0U>>1,0,W[i]};v[V[i]].push_back(cur); G[cur++] = (E){V[i],U[i],0,0,-W[i]};}//for (int i = 0; i < 4*m; i++) G[i].flow = 0; flow = 0; //int x = 0;while (SPFA());printf("%d",cost);return 0;
}
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！