open ios class std push mage style def 题目
a
看完题目,根本没想法,暴力的复杂度是指数级别的,枚举所有的集合,当时有点紧张,暴力的都没写,其实没思路的
时候最好写暴力的算法,骗点分就可以了。后来,看了牛客网上大神的思路,然后学习了下最大流最小割的方法,这题的
做法就是枚举源点和汇点,跑最大流算法,然后用流量更新答案,同时保存最小割,最后输出,就可以了。
简单写了下,也是无法实际运行去判断正误。
对最大流最小割的思路理解的不是很透彻,不知道怎么求最小割,没有做这方面的练习。
- #include <iostream>
- #include <cstdio>
- #include <cstring>
- #include <queue>
- #include <cmath>
- #include <algorithm>
- using namespace std;
- const int mn=422;
- const int mm=10000;
- const double oo=999999;
- int node, st, sd, edge;
- int reach[mm], nxt[mm];
- double flow[mm];
- int adj[mn], work[mn], dis[mn], que[mn], cap[mn];
- inline void init(int _node, int _st, int _sd)
- {
- node=_node, st=_st, sd=_sd;
- for(int i=0; i<node; i++)
- adj[i]=-1;
- edge=0;
- }
- inline void addedge(int u, int v, double c1, double c2)
- {
- reach[edge]=v, flow[edge]=c1, nxt[edge]=adj[u], cap[edge] = c1, adj[u]=edge++;
- reach[edge]=u, flow[edge]=c2, nxt[edge]=adj[v], cap[edge] = c2, adj[v]=edge++;
- }
- bool bfs()
- {
- int i,u,v,l,r=0;
- for(i=0; i<node; ++i)dis[i]=-1;
- dis[que[r++]=st]=0;
- for(l=0; l<r; ++l)
- for(i=adj[u=que[l]]; i>=0; i=nxt[i])
- if(flow[i]&&dis[v=reach[i]]<0)
- {
- dis[que[r++]=v]=dis[u]+1;
- if(v==sd)return 1;
- }
- return 0;
- }
- typedef pair<int, int> pii;
- vector<pii> getCut() {
- int l, r = 0, u, v;
- que[r++] = st;
- vector<pii> res;
- vector<bool> in(node, 0);
- for (l = 0; l < r; l++) {
- if(in[que[l] ]) continue;
- in[que[l] ] = 1;
- for (int i = adj[u = que[l]]; i >= 0; i = nxt[i]) {
- //cout << reach[i] <<" ";
- if(flow[i] != 0) {
- que[r++] = reach[i];
- } else {
- int x = u, y = reach[i];
- if(x > y) swap(x, y);
- res.push_back({x, y});
- }
- }
- //cout << endl;
- }
- return res;
- }
- double dfs(int u,double exp)
- {
- if(u==sd) return exp;
- double tmp;
- for(int &i=work[u],v; i>=0; i=nxt[i])
- if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=dfs(v,min(exp,flow[i])))>0)
- {
- flow[i]-=tmp;
- flow[i^1]+=tmp;
- return tmp;
- }
- return 0;
- }
- double Dinic()
- {
- double max_flow=0, flow;
- while(bfs())
- { //cout << "asd" << endl;
- for(int i=0; i<node; i++) work[i]=adj[i];
- while(flow=dfs(st,oo)) {
- //cout << flow << endl;
- max_flow+=flow;
- }
- }
- return max_flow;
- }
- //上面从网上搜索的,注意修改顶点数,边数,这里边数是2倍,注意节点的编号,从0开始。
- //当然,你必须知道dinic算法的逻辑才行。
- struct Node {
- int x, y, v;
- };
- int main()
- {
- freopen("test.in", "r", stdin);
- int n, m;
- scanf("%d%d",&n,&m);
- int x, y, v;
- vector<Node> e;
- for (int i = 0; i < m; i++) {
- scanf("%d%d%d", &x, &y, &v);
- e.push_back({x, y, v});
- }
- int res = INT_MAX;
- vector<pii> p;
- for (int i = 1; i <= n; i++) {
- for (int j = i + 1; j <= n; j++) {
- init(n + 1, i, j);
- for (Node t : e) {
- addedge(t.x, t.y, t.v, t.v);
- }
- double ans=Dinic();
- if(ans < res) {
- res = ans;
- p = getCut();
- }
- }
- }
- //cout << res << endl;
- sort(p.begin(), p.end());
- for (pii t : p)
- cout << t.first << " " << t.second << endl;
- return 0;
- }
最大流最小割一题
来源: http://www.bubuko.com/infodetail-2320300.html