//神一样的思想,神一样的代码,我佩服的五体投地!! //题目给出五个正整数n,m,k,s,t。n表示n星球,m表示m个双向隧道, //k,s,t表示要把k个电脑从s星球运到t星球,双向道只能单行,走一条 //道用时一天,求最短时间,并输出运输方案。 //分析: //假定T天可以运完,可以吧每个点u拆分成T+1个,分别为u0,u1。。。 //u0是初始状态,u1是一天后的状态,对于相邻的a,b。a0到b1有一条 //容量为1的边,b0到a1也有一条,a0到a1有一天容量为INF的路,表示不动。 //用模板求出最大流,如果达到了k就输出T,达不到就T++; #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> using namespace std; const int maxn = 5000 + 10; const int INF = 1000000000; struct Edge { int from, to, cap, flow; }; bool operator < (const Edge& a, const Edge& b) { return a.from < b.from || (a.from == b.from && a.to < b.to); } struct Dinic { int n, m, s, t; vector<Edge> edges; // 边数的两倍 vector<int> G[maxn]; // 邻接表,G[i][j]表示结点i的第j条边在e数组中的序号 bool vis[maxn]; // BFS使用 int d[maxn]; // 从起点到i的距离 int cur[maxn]; // 当前弧指针 void init() { edges.clear(); } void clearNodes(int a, int b) { for(int i = a; i <= b; i++) G[i].clear(); } void AddEdge(int from, int to, int cap) { edges.push_back((Edge){from, to, cap, 0}); edges.push_back((Edge){to, from, 0, 0}); m = edges.size(); G[from].push_back(m-2); G[to].push_back(m-1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue<int> Q; Q.push(s); vis[s] = 1; d[s] = 0; while(!Q.empty()) { int x = Q.front(); Q.pop(); for(int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } int DFS(int x, int a) { if(x == t || a == 0) return a; int flow = 0, f; for(int& i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if(d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap-e.flow))) > 0) { e.flow += f; edges[G[x][i]^1].flow -= f; flow += f; a -= f; if(a == 0) break; } } return flow; } // 求s-t最大流。如果最大流超过limit,则只找一个流量为limit的流 int Maxflow(int s, int t, int limit) { this->s = s; this->t = t; int flow = 0; while(BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, limit - flow); if(flow == limit) break; // 达到流量限制,直接退出 } return flow; } }; Dinic g; const int maxm = 200 + 10; int main() { int n, m, k, S, T; int u[maxm], v[maxm]; // 输入边 while(scanf("%d%d%d%d%d", &n, &m, &k, &S, &T) == 5) { for(int i = 0; i < m; i++) scanf("%d%d", &u[i], &v[i]); g.init(); int day = 1; g.clearNodes(0, n-1); // 第一层结点编号为0~n-1。第day层(day>=1)结点编号为day*n~day*n+n-1 int flow = 0; for(;;) { // 判断day天是否有解 // 一架飞船最多需要n-1天到达目的地,沿着这一路线最多需要n+k-2天就可以运完所有飞船,总结点数不超过(n+k-1)n g.clearNodes(day*n, day*n+n-1); for(int i = 0; i < n; i++) g.AddEdge((day-1)*n+i, day*n+i, INF); // 原地不动 for(int i = 0; i < m; i++) { g.AddEdge((day-1)*n+u[i]-1, day*n+v[i]-1, 1); // u[i]->v[i] g.AddEdge((day-1)*n+v[i]-1, day*n+u[i]-1, 1); // v[i]->u[i] } flow += g.Maxflow(S-1, day*n+T-1, k - flow);//第0天的源点,到第n天的汇点 if(flow == k) break; day++; } // 输出解 printf("%d\n", day); int idx = 0; vector<int> location(k, S); // 每架飞船的当前位置 for(int d = 1; d <= day; d++) { idx += n*2;//前2*n个点是自己通向自己的流量(不动时),应该跳过。 vector<int> moved(k, 0); // 第d天有没有移动飞船i vector<int> a, b; // 第d天有一架飞船从a[i]到b[i] for(int i = 0; i < m; i++) {//接下来就是2*m个两个不同的点的流量 int f1 = g.edges[idx].flow; idx += 2; int f2 = g.edges[idx].flow; idx += 2; if(f1 == 1 && f2 == 0) { a.push_back(u[i]); b.push_back(v[i]); } if(f1 == 0 && f2 == 1) { a.push_back(v[i]); b.push_back(u[i]); } } printf("%d", a.size());//第d天走的飞船数 for(int i = 0; i < a.size(); i++) { // 查找是哪架飞船从a[i]移动到了b[i] for(int j = 0; j < k; j++)//模拟一下整个移动过程 if(!moved[j] && location[j] == a[i]) { printf(" %d %d", j+1, b[i]); moved[j] = 1; location[j] = b[i]; break; } } printf("\n"); } } return 0; }
相关推荐
已知两个单链表 LA 和 LB 分别表示两个集合,其元素递增排序,设计算法求出 LA 和 LB 的交集 C ,要求 C 同样以元素递增的单链表形式存储。
针对斜沟煤矿选煤厂8#、13#气煤不易泥化的特点,采用LA1450-B型重介质旋流器对其进行分选。介绍了该旋流器的结构、工作原理、技术特点、主要技术参数,并分析了其在现场的应用情况。生产实践说明,采用该旋流器作为主再...
ALPS 高级车载收音头 TFTC4-b3 高频调谐电路 LA1787高频头电路原理图 LA1787资料
行驶工况CYC_LA92
114la 源码114la 源码114la 源码114la 源码114la 源码114la 源码114la 源码114la 源码
实验用例: 已知函数y=f(x)的一张表,要求利用Lagrange插值多项式 求被插值函数f(x)在点x=65处的近似值
目前最完整的仿114la导航程序 去除所有垃圾广告代码,网址清爽干净, 是目前最流行的网址导航,并且带完整后台管理。是目前最完整的仿114la导航程序 优化了首页显示速度 0.基本功能:大字版,24城市+自动识别ip跳到...
单片线性集成电路 LA1260 FM/AM 收音机集成电路 自己翻译的。有不足之处请谅解。
Labella.js 是 Twitter 开源的时间轴标签放置工具,可以把标签没有重叠的放在时间轴上。“标签也可以很美丽”在线演示:http://twitter.github.io/labella.js/ 示例代码:// idealPos: The most preferred ...
德力西 LA2、LA18、LA19系列按钮开关 技术说明书rar,德力西 LA2、LA18、LA19系列按钮开关 技术说明书
LA2016逻辑分析仪 上层解析软件和驱动
讲述了实验室A2LA申请流程,详细的讲述了在A2LA申请的步骤
1. Kingst LA2016软件 2. Kingst LA2016快速使用说明 3. Kingst LA2016详细使用说明 4. Kingst LA2016视频
IS868LA2是ASM做手机传感器最好的固晶机
在中子分离能以下测量了138 La和139 La的γ射线强度函数和核能级密度。 这些新数据用于计算天体物理麦克斯韦平均截面(n,γ),以研究光解过程中p核138 La的产生和破坏。 结果证实,相对于观测到的丰度,p-过程中...
正泰LA2、LA4系列按钮开关pdf,正泰LA2、LA4系列按钮开关
将所有在线性表Lb中但不在La中的数据元素插入到La中
la3450 pdf 数据手册 la3450 pdf 数据手册 la3450 pdf 数据手册
一款彩色电视机原理图 PDF格式 主芯片 LA76930 声块LA7845
介绍了LUDOWICI生产的LA1450-B型大直径有压两产品重介旋流器的设计特点及影响分选效果的关键因素,通过理论计算和实践应用确定了分选密度、入料压力、干煤泥处理量和重介质的质量是影响旋流器应用效果的关键参数,并...