首页 > 代码库 > 团队出游问题 网易有道
团队出游问题 网易有道
有道目前崇尚小团队开发工作，因为团队越小，工作效率越高，团队之间不可避免存在合作，为了把高内聚低耦合的思想用在工作中，略去。
分析：输入定点数，边数，顶点一和顶点二，以及所有的边，刚开始以为是，找到最短路，然后记录路径，进行统计，发现这个搜索就行，再仔细一想，有源点和汇点，这不是最大流最小割么！然后，发现不会写dinic算法，之前写过，就是一个深搜加广搜，然后就完了，但是现场这么紧张的写，是写不出来的，所以从网上直接找模板做吧。
1. 刚开始，添加源点和汇点，到输入的一对顶点，这个边上的流量设为100 + 10，其他输入的边的流量为1，然后就去交了，完全错误，错误的原因是：我自己把它当做有向图来处理的。其实是无向图，修改后过了80%，后来也没调出来，就结束了。
考试结束后仔细分析下：
1.这个图是无向图，使用最大流最小割的时候注意边上流量的设置。这个题目能用普通的枚举做法么，要是可以，应该怎么枚举。
2.题意强调任何2个团队只有一个接口人，这个描述应该包含很多性质吧，我不知道怎么做，这个性质应该怎么利用，图是无向图，没有出边和入边的概念。
3.由于去掉一个点，就是去掉一个团队，这样这个点应该有流量为1的限制，所以给每一个顶点（除去源点和汇点）后面添加一条边和一个点，这条边的流量应该为1.注意源点和汇点要单独处理。
4. 由于是无向图，给定的2个顶点，任意一个顶点作为源点或者汇点都可以，还是怎么做？这个也不知道怎么处理。
我想到的几点就上面这样，也没有地方去测试程序的正确性，如果你能找到原题，请告知！就这样吧。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <queue> 5 #include <cmath> 6 #include <algorithm> 7 using namespace std; 8 9 const int mn=422; 10 const int mm=10000; 11 const double oo=999999; 12 int node, st, sd, edge; 13 int reach[mm], nxt[mm]; 14 double flow[mm]; 15 int adj[mn], work[mn], dis[mn], que[mn]; 16 17 inline void init(int _node, int _st, int _sd) 18 { 19 node=_node, st=_st, sd=_sd; 20 for(int i=0; i<node; i++) 21 adj[i]=-1; 22 edge=0; 23 } 24 25 inline void addedge(int u, int v, double c1, double c2) 26 { 27 reach[edge]=v, flow[edge]=c1, nxt[edge]=adj[u],adj[u]=edge++; 28 reach[edge]=u, flow[edge]=c2, nxt[edge]=adj[v],adj[v]=edge++; 29 } 30 31 bool bfs() 32 { 33 int i,u,v,l,r=0; 34 for(i=0; i<node; ++i)dis[i]=-1; 35 dis[que[r++]=st]=0; 36 for(l=0; l<r; ++l) 37 for(i=adj[u=que[l]]; i>=0; i=nxt[i]) 38 if(flow[i]&&dis[v=reach[i]]<0) 39 { 40 dis[que[r++]=v]=dis[u]+1; 41 if(v==sd)return 1; 42 } 43 return 0; 44 } 45 46 double dfs(int u,double exp) 47 { 48 if(u==sd) return exp; 49 double tmp; 50 for(int &i=work[u],v; i>=0; i=nxt[i]) 51 if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=dfs(v,min(exp,flow[i])))>0) 52 { 53 flow[i]-=tmp; 54 flow[i^1]+=tmp; 55 return tmp; 56 } 57 return 0; 58 } 59 60 double Dinic() 61 { 62 double max_flow=0, flow; 63 while(bfs()) 64 { //cout << "asd" << endl; 65 for(int i=0; i<node; i++) work[i]=adj[i]; 66 while(flow=dfs(st,oo)) { 67 //cout << flow << endl; 68 max_flow+=flow; 69 } 70 } 71 return max_flow; 72 } 73 //上面从网上搜索的，注意修改顶点数，边数，这里边数是2倍，注意节点的编号，从0开始。 74 //当然，你必须知道dinic算法的逻辑才行。 75 int main() 76 { 77 freopen("test.in", "r", stdin); 78 int n, m, k, t1, t2; 79 scanf("%d%d%d%d",&n,&m,&t1, &t2); 80 int s, e; 81 int len = n; 82 s = 0; e = n * 2 + 1; 83 n = n * 2 + 2; 84 85 init(n,s,e); 86 addedge(s, t1 + len, 150, 0); 87 addedge(t2, e, 150, 0); 88 for (int i = 1; i <= len; i++) { 89 //if(i == t1 || i == t2) continue; 90 addedge(i, i + len, 1, 1); 91 //cout << i << " " << i + len << endl; 92 } 93 int x, y; 94 for (int i = 0; i < m; i++) { 95 scanf("%d%d", &x, &y); 96 97 addedge(x + len, y, 1, 1); 98 //cout << x + len << " " << y << endl; 99 }100 double ans=Dinic();101 printf("%d\n",(int)ans);102 103 return 0;104 }
团队出游问题 网易有道
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。