| Problem F |
Data Flow |
| Time Limit |
5 Seconds |
In the latest Lab of IIUC, it requires to send huge amount of data from the local server to the terminal server. The lab setup is not yet ready. It requires to write a router program for the best path of data. The problem is all links of the network has a fixed capacity and cannot flow more than that amount of data. Also it takes certain amount of time to send one unit data through the link. To avoid the collision at a time only one data unit can travel i.e. at any instant more than one unit of data cannot travel parallel through the network. This may be time consuming but it certainly gives no collision. Each node has sufficient buffering capability so that data can be temporarily stored there. IIUC management wants the shortest possible time to send all the data from the local server to the final one.
FZ http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vciBleGFtcGxlLCBpbiB0aGUgYWJvdmUgbmV0d29yayBpZiBhbnlvbmUgd2FudHMgdG8gc2VuZCAyMCB1bml0IGRhdGEgZnJvbSBBIHRvIEQsIGhlIHdpbGwgc2VuZCAxMCB1bml0IGRhdGEgdGhyb3VnaCBBRCBsaW5rIGFuZCB0aGVuIDEwIHVuaXQgZGF0YSB0aHJvdWdoIEFCLUJEIGxpbmsgd2hpY2ggd2lsbCB0YWtlIDEwJiM0Mzs3MD04MCB1bml0IHRpbWUuPC9wPgo8cD4gPC9wPgo8cD48c3Ryb25nPklucHV0PC9zdHJvbmc+PC9wPgo8cD5FYWNoIGlucHV0IHN0YXJ0cyB3aXRoIHR3byBwb3NpdGl2ZSBpbnRlZ2VycyA8c3Ryb25nPk4gKDIgPC9zdHJvbmc+odwgPHN0cm9uZz5OIDwvc3Ryb25nPqHcIDxzdHJvbmc+MTAwKSwgTSAoMSA8L3N0cm9uZz6h3CA8c3Ryb25nPk0gPC9zdHJvbmc+odwgPHN0cm9uZz41MDAwKTwvc3Ryb25nPi4gSW4gbmV4dCBmZXcgbGluZXMgdGhlIGxpbmsgYW5kIGNvcnJlc3BvbmRpbmcgcHJvcGFnYXRpb24gdGltZSB3aWxsIGJlIGdpdmVuLiBUaGUgbGlua3MgYXJlCiBiaWRpcmVjdGlvbmFsIGFuZCB0aGVyZSB3aWxsIGJlIGF0IG1vc3Qgb25lIGxpbmsgYmV0d2VlbiB0d28gbmV0d29yayBub2Rlcy4gSW4gbmV4dCBsaW5lIHRoZXJlIHdpbGwgYmUgdHdvIHBvc2l0aXZlIGludGVnZXJzIDxzdHJvbmc+RCwgSzwvc3Ryb25nPiB3aGVyZSA8c3Ryb25nPkQ8L3N0cm9uZz4gaXMgdGhlIGFtb3VudCBvZiBkYXRhIHRvIGJlIHRyYW5zZmVycmVkIGZyb20gMTxzdXA+c3Q8L3N1cD4gdG8gPHN0cm9uZz5OPC9zdHJvbmc+"th node and K is the link capacity. Input is terminated by EOF.
Output
For each dataset, print the minimum possible time in a line to send all the data. If it is not possible to send all the data, print "Impossible.". The time can be as large as 1015.
| Sample Input |
Output for Sample Input |
4 5 1 4 1 1 3 3 3 4 4 1 2 2 2 4 5 20 10 4 4 1 3 3 3 4 4 1 2 2 2 4 5 20 100 4 4 1 3 3 3 4 4 1 2 2 2 4 5 20 1 |
80 140 Impossible. |
题意：给定n个点，m条边和运输时间，给定要运的货物D和边的容量K求运送最少时间。
思路：最大流最小费用。。模版题。源点与1连容量为D，汇点为n。
代码:
#include#include #define INFF 0x3f3f3f3f3f3f3f #define INF 0x3f3f3f3f #include using namespace std; const int N = 105, M = 50005; long long value[M], cost[M]; int n, m, A[M], B[M], D, K, E, first[N], next[M], u[M], v[M], pe[N], pv[N], a[N], f[M], w[M], s, t; queue q; void add(int a, int b, int value, long long time) { u[E] = a; v[E] = b; w[E] = value; cost[E] = time; next[E] = first[u[E]]; first[u[E]] = E ++; u[E] = b; v[E] = a; w[E] = 0; cost[E] = -time; next[E] = first[u[E]]; first[u[E]] = E ++; } void init() { E = s = 0, t = n; memset(first, -1, sizeof(first)); for (int i = 0; i < m; i ++) scanf("%d%d%lld", &A[i], &B[i], &value[i]); scanf("%d%d", &D, &K); for (int i = 0; i < m; i ++) { add(A[i], B[i], K, value[i]); add(B[i], A[i], K, value[i]); } add(s, 1, D, 0); } void solve() { init(); bool vis[N]; long long d[N], C = 0; int F = 0; memset(f, 0, sizeof(f)); while(1) { for (int i = 0; i <= n; i ++) d[i] = INFF; d[s] = 0; memset(vis, 0, sizeof(vis)); q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); vis[u] = 0; for (int e = first[u]; e != -1; e = next[e]) { if (w[e] > f[e] && d[v[e]] > d[u] + cost[e]) { d[v[e]] = d[u] + cost[e]; pv[v[e]] = u; pe[v[e]] = e; if (!vis[v[e]]) { vis[v[e]] = 1; q.push(v[e]); } } } } if (d[t] == INFF) break; int a = INF; for (int v = t; v != s; v = pv[v]) a = min(a, w[pe[v]] - f[pe[v]]); for (int v = t; v != s; v = pv[v]) { f[pe[v]] += a; f[pe[v]^1] -= a; } C += d[t] * a; F += a; } if (F < D) printf("Impossible.\n"); else printf("%lld\n", C); } int main() { while (~scanf("%d%d", &n, &m)) { solve(); } return 0; }