首页 > 代码库 > SCU 4442 Party
SCU 4442 Party
二分图的最小点权覆盖。
非常感谢巨巨@islands_的解答，还帮我画了一个图。
题目保证给出的边构成的图是一个二分图。
如果没有第三种类型的$frog$，那么问题就很简单了。即选择哪些点，覆盖住所有的边，并且要求选择的点的权值之和最小。可以转换成网络流来解决。
现在有第三种类型的$frog$，可以把这种$frog$拆成两个点，两点之间连边，然后其余和他有矛盾的点，分别向两个点中的一个点连边。画画图可以发现拆点之后的新图也是二分图。对这个图跑一次二分图的最小点权覆盖，如果拆点的边两端有一个点被选择，说明这个$frog$实际上是不选择的，如果拆点的边两端有两个点被选择，说明这个$frog$实际上被选择了，那么只要在结果上减去第三种类型的$frog$的权值和就可以了。
#include<bits/stdc++.h>using namespace std;int n,m;int w[2010],p[2010],dis[2010];vector<int>g[2010];const int maxn = 2100 + 10;const int INF = 0x7FFFFFFF;struct Edge{ int from, to, cap, flow; Edge(int u, int v, int c, int f) :from(u), to(v), cap(c), flow(f){}};vector<Edge>edges;vector<int>G[maxn];bool vis[maxn];int d[maxn];int cur[maxn];int s, t;void init(){ for (int i = 0; i < maxn; i++) G[i].clear(); edges.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)); int w = edges.size(); G[from].push_back(w - 2); G[to].push_back(w - 1);}bool BFS(){ memset(vis, 0, sizeof(vis)); queue<int>Q; Q.push(s); d[s] = 0; vis[s] = 1; 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) { edges[G[x][i]].flow+=f; edges[G[x][i] ^ 1].flow-=f; flow+=f; a-=f; if(a==0) break; } } if(!flow) d[x] = -1; return flow;}int dinic(int s, int t){ int flow = 0; while (BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow;}void B(int x){ queue<int>Q; Q.push(x); dis[x]=0; while(!Q.empty()) { x = Q.front(); Q.pop(); for(int i=0;i<g[x].size();i++) { int to = g[x][i]; if(dis[to]!=-1) continue; dis[to] = dis[x]^1; Q.push(to); } }}void ADD(int a,int b){ g[a].push_back(b); g[b].push_back(a);}int main(){ while(~scanf("%d%d",&n,&m)) { for(int i=1;i<=2*n;i++) g[i].clear(); for(int i=1;i<=n;i++) scanf("%d",&w[i]); for(int i=1;i<=n;i++) { scanf("%d",&p[i]); if(p[i]==3) ADD(i,i+n); } for(int i=1;i<=m;i++) { int A,B; scanf("%d%d",&A,&B); if(p[A]+p[B]==3) continue; if(p[A]==1||p[A]==2) { if(p[B]==1||p[B]==2) ADD(A,B); else { if(p[A]==1) ADD(A,B); else ADD(A,B+n); } } else if(p[A]==3) { if(p[B]==1||p[B]==2) { if(p[B]==1) ADD(A,B); else ADD(A+n,B); } else if(p[B]==3) { ADD(A,B); ADD(A+n,B+n); } } } memset(dis,-1,sizeof dis); for(int i=1;i<=2*n;i++) { if(dis[i]!=-1) continue; B(i); } init(); s=0,t=2*n+1; for(int i=1;i<=2*n;i++) { if(dis[i]==1) continue; for(int j=0;j<g[i].size();j++) AddEdge(i,g[i][j],INF); } for(int i=1;i<=2*n;i++) { int V; if(i<=n) V = w[i]; else V=w[i-n]; if(dis[i]==0) AddEdge(s,i,V); else AddEdge(i,t,V); } int ans = dinic(s,t); for(int i=1;i<=n;i++) if(p[i]==3) ans=ans-w[i]; printf("%d\n",ans); } return 0;}
SCU 4442 Party
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。