bzoj4514 数字配对
程序员文章站
2022-05-11 14:11:13
思路
首先想到费用流。
对于每个点拆点。然后考虑我们怎样才能保证每个点只被用一次。
如果$i$与$j$满足条件。那么就从$i$向$j$连一条边并且从$j$向$i$连一条 ......
思路
首先想到费用流。
对于每个点拆点。然后考虑我们怎样才能保证每个点只被用一次。
如果\(i\)与\(j\)满足条件。那么就从\(i\)向\(j\)连一条边并且从\(j\)向\(i\)连一条边。这样每次增广的时候我们都可以看作某一条边被增广了两次。显然从\(i\)到\(j\)和从\(j\)到\(i\)的边是等价的。也就是说,如果当前增广这两个点之间的边更优秀,那么在增广完成从\(i\)到\(j\)和从\(j\)到\(i\)这两条边流量变为\(0\)之前不回去增广其他的边。
比较难解释,仔细想一下可以发现是对的。这样最后我们找出的流量实际上是答案的两倍。除二即可。
然后还要考虑题目中对于价值的限制。我们把价值当作费用,每次增广费用最大的路径。直到如果再增广费用变为负数为止。
代码
/* * @author: wxyww * @date: 2019-02-17 14:52:25 * @last modified time: 2019-02-17 19:36:45 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int n = 410,m = 1000000 + 100,inf = 1e9; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int v,nxt,w; ll cost; }e[m]; int head[n],ejs = 1; void add(int u,int v,int w,ll c) { e[++ejs].v = v;e[ejs].w = w;e[ejs].cost = c;e[ejs].nxt = head[u];head[u] = ejs; e[++ejs].v = u;e[ejs].w = 0;e[ejs].cost = -c;e[ejs].nxt = head[v];head[v] = ejs; } int a[n],vis[n],fa[n],b[n]; ll dis[n],c[n]; queue<int>q; int s,t; bool pd(int x,int y) { if(x < y) swap(x,y); if(!y || x == y) return false; if(x % y) return false; int k = x/y; for(int i = 2;i * i <= k;++i) if(k % i == 0) return false; return true; } bool spfa() { while(!q.empty()) q.pop(); memset(dis,-0x3f,sizeof(dis)); memset(vis,0,sizeof(vis)); memset(fa,0,sizeof(fa)); q.push(s);dis[s] = 0; while(!q.empty()) { int u = q.front();q.pop();vis[u] = 0; for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(dis[v] < dis[u] + e[i].cost && e[i].w) { dis[v] = dis[u] + e[i].cost; fa[v] = i; if(!vis[v]) q.push(v),vis[v] = 1; } } } return fa[t]; } ll dinic() { ll cost = 0,flow = 0; while(spfa()) { int mn = inf; for(int i = fa[t];i;i = fa[e[i ^ 1].v]) mn = min(mn,e[i].w); for(int i = fa[t];i;i = fa[e[i ^ 1].v]) e[i].w -= mn,e[i ^ 1].w += mn; if(cost + dis[t] * mn < 0) { flow += cost / -dis[t]; return flow; } cost += dis[t] * mn; flow += mn; } return flow; } int main() { int n = read(); for(int i = 1;i <= n;++i) a[i] = read(); for(int i = 1;i <= n;++i) b[i] = read(); for(int i = 1;i <= n;++i) c[i] = read(); s = n * 2 + 1,t = s + 1; for(int i = 1;i <= n;++i) for(int j = 1;j <= n;++j) if(i != j && pd(a[j],a[i])) add(i,j + n,inf,c[i] * c[j]); int tot = ejs; for(int i = 1;i <= n;++i) add(s,i,b[i],0); for(int i = 1;i <= n;++i) add(i + n,t,b[i],0); cout<<(dinic() >> 1); return 0; }
上一篇: 数组奇偶数分组