本文主要是介绍家园 wiki 1034，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
网络流+拆点。
假设有n个空间站，每个站每过一秒，就会在分出来一个点，表示这一秒的空间站。假如有三个空间站a，b，c。第0秒整个图就是由超级源点，地球，空间站a，b，c，汇点。第一秒的时候多了a1，b1，c1三个点。由于空间站容量无限大，因此a->a1的边应该是容量为无限大，同理b到b1，c到c1也是。如果有飞机第零秒从a飞到b，则a到b1连一条边，容量为该飞机的容量。以上就是建图方法。
我的AC代码：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <queue>
#include <vector>
using namespace std;
struct Edge{int from,to,cap,flow;
};
#define INT_MAX 0x07777777
int n,m,k,s,t,result,sz;
int c[50],pre[50],now[50],changdu[50];
int p[50000],a[50000],inq[50000];
int route[20][20];
vector<Edge> es;
vector<int> G[50000];
void AddEdge(int from, int to, int cap){es.push_back(Edge{from,to,cap,0});es.push_back(Edge{to,from,0,0});int num = es.size();G[from].push_back(num-2);G[to].push_back(num-1);
}
void init(){scanf("%d%d%d",&n,&m,&k);memset(route, -1, sizeof(route));for(int i = 0; i < m; i++){scanf("%d %d",&c[i], &changdu[i]);for(int j = 0; j < changdu[i]; j++){scanf("%d", &route[i][j]);if (route[i][j]==-1) {route[i][j] = n+2;}else{route[i][j]++;}}}s = 0;t = n+2;AddEdge(0, 1, k);for (int i = 0; i <= n+2; i++) {now[i] = i;}sz = n+3;
}
void solve(){int curtime = 0;while (curtime < 200) {for(int i = 0; i <= n+2; i++) pre[i] = now[i];for(int i = 1; i < n+2; i++) {now[i] = sz; sz++;}for(int i = 0; i < m; i++){int cur = curtime % changdu[i];int next = (cur==changdu[i]-1 ? 0 : cur+1);if (route[i][cur]==n+2) {continue;}AddEdge(pre[route[i][cur]], now[route[i][next]], c[i]);}for(int i = 1; i < n+2; i++){AddEdge(pre[i], now[i], INT_MAX);}//for(int i = 0; i < es.size(); i++) es[i].flow = 0;memset(p, -1, sizeof(p));memset(a, 0, sizeof(a));a[0] = INT_MAX;queue<int> q;q.push(0);//result = 0;while (true) {memset(a, 0, sizeof(a));a[0] = INT_MAX;q.push(0);while (!q.empty()) {int u = q.front();q.pop();for(int i = 0; i < G[u].size(); i++){Edge& e = es[G[u][i]];if(e.cap > e.flow && !a[e.to]){a[e.to] = (a[e.from] < e.cap-e.flow ? a[e.from] : e.cap-e.flow);q.push(e.to);p[e.to] = G[u][i];}}}if(a[t]==0) break;int u = t;while (u) {es[p[u]].flow += a[t];es[p[u]^1].flow -= a[t];u = es[p[u]].from;}result += a[t];}curtime++;if (result>=k) {printf("%d\n",curtime);break;}}if (curtime==200) {printf("%d\n",0);}
}
int main(int argc, const char * argv[])
{init();solve();
}这篇关于家园 wiki 1034的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
