如何做app 的模板下载网站,网站建设费用评估,电商网站开发成本,建设银行网站不能打开[HZNOI #514] Magic 题意 给定一个 \(n\) 个点 \(m\) 条边的有向图, 每个点有两个权值 \(a_i\) 和 \(b_i\), 可以以 \(b_i\) 的花费把第 \(i\) 个点的 \(a_i\) 变成 \(0\). 最后每个点 \(i\) 产生的花费为所有从 \(i\) 出发能通过一条有向边直接到达的点 \(j\) 的 \(a_j\) 的 \… [HZNOI #514] Magic 题意 给定一个 \(n\) 个点 \(m\) 条边的有向图, 每个点有两个权值 \(a_i\) 和 \(b_i\), 可以以 \(b_i\) 的花费把第 \(i\) 个点的 \(a_i\) 变成 \(0\). 最后每个点 \(i\) 产生的花费为所有从 \(i\) 出发能通过一条有向边直接到达的点 \(j\) 的 \(a_j\) 的 \(\max\). 最小化这个过程中的总花费. \(n\le 1000,m\le50000\) 题解 一点都不套路的最小割. 果然我是不会网络流的. 对于每个点, 如果将它的邻接点按照 \(a_j\) 降序排序的话, 不难发现必然要干掉一个前缀的所有 \(a_j\) 才能让这个点在最后统计的时候产生的花费变小. 但是多次干掉同一个点不能重复计算花费. 那么我们一点都不自然地想到最小割. 先把所有点拆成两个, 一个负责计算最终统计时的花费 (A类点), 一个负责计算被干掉的时候产生的花费 (B类点). 被干掉的时候产生的花费直接连一条流量为 \(b_i\) 的边到 \(t\) 就可以了. 最终统计时的花费先从 \(s\) 连一条 \(\infty\) 边到当前点, 然后按照 \(a_j\) 降序拉出一条链来, 链上的每个点代表一条边, 权值为这条边到达的点的 \(a_j\). 然后再从链上的每个点连一条 \(\infty\) 边到 \(j\) 对应的点. 这样的话如果 \(s\verb|-|t\) 被割断, 那么对于每一个 A 类点, 后面必然是割掉了某个 \(a_j\), 同时所有大于被割断的 \(a_j\) 的边邻接的点必然都已经被割掉了 \(b_i\). 建图Dinic就可以了. 这个拉链然后最小割的套路依然没有学会...果然我还是太菜了QAQ... 什么你问我 \(nm\) 个点Dinic怎么跑过去的? 我怎么知道?Dinic的运行速度大概都是靠信仰吧... 恋恋世界第一! 参考代码 #include bits/stdc.hconst int MAXV1e510;
const int MAXE5e610;
const int INF0x7FFFFFFF;struct Edge{int from;int to;int flow;Edge* rev;Edge* next;
};
Edge E[MAXE];
Edge* head[MAXV];
Edge* cur[MAXV];
Edge* topE;int v;
int e;
int a[1010];
int b[1010];
int depth[MAXV];
std::vectorint link[1010];bool BFS(int,int);
int Dinic(int,int);
int DFS(int,int,int);
void Insert(int,int,int);int main(){freopen(magic.in,r,stdin);freopen(magic.out,w,stdout);scanf(%d%d,v,e);for(int i1;iv;i)scanf(%d,ai);for(int i1;iv;i)scanf(%d,bi);for(int i0;ie;i){int a,b;scanf(%d%d,a,b);link[a].push_back(b);}for(int i1;iv;i)std::sort(link[i].begin(),link[i].end(),[](int a,int b){return ::a[a]::a[b];});int s0,t1,cntv*21;for(int i1;iv;i){Insert(s,i1,INF);Insert(iv1,t,b[i]);int lasti1;for(size_t j0;jlink[i].size();j){cnt;Insert(cnt,vlink[i][j]1,INF);Insert(last,cnt,a[link[i][j]]);lastcnt;}}printf(%d\n,Dinic(s,t));return 0;
}int Dinic(int s,int t){int ans0;while(BFS(s,t))ansDFS(s,INF,t);return ans;
}bool BFS(int s,int t){memset(depth,0,sizeof(depth));std::queueint q;q.push(s);depth[s]1;cur[s]head[s];while(!q.empty()){sq.front();q.pop();for(Edge* ihead[s];i!NULL;ii-next){if(i-flow0depth[i-to]0){depth[i-to]depth[s]1;cur[i-to]head[i-to];if(i-tot)return true;q.push(i-to);}}}return false;
}int DFS(int s,int flow,int t){if(st||flow0)return flow;int restflow;for(Edge* icur[s];i!NULL;ii-next){if(i-flow0depth[i-to]depth[s]1){int tmpDFS(i-to,std::min(rest,i-flow),t);if(tmp0)depth[i-to]0;rest-tmp;i-flow-tmp;i-rev-flowtmp;if(rest0)break;}}return flow-rest;
}inline void Insert(int from,int to,int flow){top-fromfrom;top-toto;top-flowflow;top-revtop1;top-nexthead[from];head[from]top;top-fromto;top-tofrom;top-flow0;top-revtop-1;top-nexthead[to];head[to]top;
}转载于:https://www.cnblogs.com/rvalue/p/10615423.html
