把每个区间的两端点按照坐标排序进行离散化。
这2n个点中的最右边的点与源点连边，即add(s,x,k,0)；最左边的点与汇点连边，即add(x,t,k,0)。
对于每个点将它与下一个点连一条容量为无穷大，费用为0的边边，即add(i,i+1,inf,0)；
对于每个区间的两端点连一条容量为1，费用为区间长度的边，即add(x,y,1,len)。
跑最大费用最大流即可。
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> #define maxn 1010 #define maxm 4005 using namespace std; const int inf=1<<30; int num,lst[maxn]; int pre[maxn],vis[maxn],flow[maxn],dis[maxn],from[maxn]; int cnt,a[maxn],b[maxn]; int s,t,n,m; queue<int>q; struct in { int to,nxt,re,w; }e[maxm]; struct node { int num,id; }p[maxn]; bool cmp(node x,node y){return x.num<y.num;} void add(int x,int y,int z,int w) { e[++num].to=y;e[num].nxt=lst[x];lst[x]=num;e[num].re=z;e[num].w=w; e[++num].to=x;e[num].nxt=lst[y];lst[y]=num;e[num].re=0;e[num].w=-w; } void clear() { num=-1; memset(lst,-1,sizeof(lst)); } int spfa() { int i,u,v; while (!q.empty()) q.pop(); for (i=1;i<=t;++i) { pre[i]=-1; from[i]=-1; dis[i]=-inf; vis[i]=0; } q.push(s); dis[s]=0; flow[s]=inf; vis[s]=1; while (!q.empty()) { u=q.front(); q.pop(); vis[u]=0; for (i=lst[u];i!=-1;i=e[i].nxt) { v=e[i].to; if (!e[i].re) continue; if (dis[v]<dis[u]+e[i].w) { dis[v]=dis[u]+e[i].w; flow[v]=min(e[i].re,flow[u]); pre[v]=i; from[v]=u; if (!vis[v]) { vis[v]=1; q.push(v); } } } } return pre[t]!=-1; } int mfmv() { int maxcost=0,maxflow=0,v; while (spfa()) { maxcost+=flow[t]*dis[t]; maxflow+=flow[t]; v=t; while (v!=s) { e[pre[v]].re-=flow[t]; e[pre[v]^1].re+=flow[t]; v=from[v]; } } return maxcost; } int main() { int i,j,n,k; clear(); scanf("%d%d",&n,&k); for (i=1;i<=n;i++) { scanf("%d%d",&a[i],&b[i]); if (a[i]>b[i]) swap(a[i],b[i]); p[++cnt].num=a[i];p[cnt].id=i; p[++cnt].num=b[i];p[cnt].id=i; } sort(p+1,p+cnt+1,cmp); s=0;t=cnt+1; add(s,1,k,0); add(cnt,t,k,0); for (i=1;i<cnt;i++) add(i,i+1,inf,0); for (i=1;i<cnt;i++) for (j=i+1;j<=cnt;j++) if (p[i].id==p[j].id) add(i,j,1,p[j].num-p[i].num); printf("%d ",mfmv()); return 0; }
把n个数按照a质因子个数的奇偶分为两类，一类与源点连边add(s,i,b[i],0)，一类与汇点连边add(i,t,b[i],0)。两类中a能够整除并在整除后得到的为质数的连边add(i,j,inf,c[i]*c[j])。
跑最大费用最大流，每次spfa后判断当前的最大费用是否为负；若为负说明此次找到的流flow[t]不能全部加入答案，此次的流应为-maxcost/dis[t]，加入答案后跳出循环。
#include<cstdio> #include<cstring> #include<queue> #include<cmath> #define maxn 205 #define maxm 100005 #define INF 1e18 using namespace std; typedef long long ll; const ll inf=1<<30; int num,lst[maxn],cur[maxn],dep[maxn]; int pre[maxn],from[maxn],vis[maxn],flow[maxn]; ll dis[maxn],c[maxn]; int a[maxn],b[maxn],odd[maxn]; int s,t,n,m; queue<int>q; struct in { int to,nxt,re; ll w; }e[maxm]; void add(int x,int y,int z,ll w) { e[++num].to=y;e[num].nxt=lst[x];lst[x]=num;e[num].re=z;e[num].w=w; e[++num].to=x;e[num].nxt=lst[y];lst[y]=num;e[num].re=0;e[num].w=-w; } void clear() { num=-1; memset(lst,-1,sizeof(lst)); } int spfa() { int i,u,v; while (!q.empty()) q.pop(); for (i=s;i<=t;i++) { pre[i]=-1; from[i]=-1; dis[i]=-INF; vis[i]=0; } q.push(s); dis[s]=0; flow[s]=inf; vis[s]=1; while (!q.empty()) { u=q.front(); q.pop(); vis[u]=0; for (i=lst[u];i!=-1;i=e[i].nxt) { v=e[i].to; if (!e[i].re) continue; if (dis[v]<dis[u]+e[i].w) { dis[v]=dis[u]+e[i].w; flow[v]=min(e[i].re,flow[u]); pre[v]=i; from[v]=u; if (!vis[v]) { vis[v]=1; q.push(v); } } } } return pre[t]!=-1; } int mfmv() { ll maxcost=0; int maxflow=0,v; while (spfa()) { if (maxcost+flow[t]*dis[t]<0) { maxflow-=maxcost/dis[t]; break; } maxcost+=flow[t]*dis[t]; maxflow+=flow[t]; v=t; while (v!=s) { e[pre[v]].re-=flow[t]; e[pre[v]^1].re+=flow[t]; v=from[v]; } } return maxflow; } int divi(int x) { int i,res=0,tmp=x; for (i=2;i*i<=x;i++) { while (tmp%i==0) { res++; tmp=tmp/i; } } if (tmp!=1) res++; return res; } int jud(int x) { if (x==2) return 1; if (x%2==0) return 0; for (int i=3;i*i<=x;i+=2) if (x%i==0) return 0; return 1; } int main() { int x,i,j,k,p; clear(); scanf("%d",&n); s=0;t=n+1; for (i=1;i<=n;i++) { scanf("%d",&a[i]); odd[i]=divi(a[i])&1; } for (i=1;i<=n;i++) scanf("%d",&b[i]); for (i=1;i<=n;i++) scanf("%lld",&c[i]); for (i=1;i<=n;i++) { if (odd[i]) add(s,i,b[i],0); else add(i,t,b[i],0); } for (i=1;i<=n;i++) for (j=1;j<=n;j++) { if (odd[i] && !odd[j]) { k=a[i];p=a[j]; if (k<p) swap(k,p); if (k%p==0 && jud(k/p)) add(i,j,inf,c[i]*c[j]); } } printf("%d ",mfmv()); return 0; }
题解参考：https://www.cnblogs.com/mrclr/p/9694664.html
#include<cstdio> #include<cstring> #include<queue> #include<cmath> #define maxn 40005 #define maxm 800005 using namespace std; const int inf=1<<30; int a[8][2]={{-2,-1},{-2,1},{-1,2},{-1,-2},{2,-1},{2,1},{1,2},{1,-2}}; int mp[205][205]; int num,lst[maxn],cur[maxn],dep[maxn]; int s,t,n,m; queue<int>q; struct in { int to,nxt,re; }e[maxm]; void add(int x,int y,int z) { e[++num].to=y;e[num].nxt=lst[x];lst[x]=num;e[num].re=z; e[++num].to=x;e[num].nxt=lst[y];lst[y]=num;e[num].re=0; } void clear() { num=-1; memset(lst,-1,sizeof(lst)); } int bfs() { int i,u,v; while (!q.empty()) q.pop(); memset(dep,-1,sizeof(dep)); dep[s]=0; q.push(s); while(!q.empty()) { u=q.front(); q.pop(); for(i=lst[u];i!=-1;i=e[i].nxt) { v=e[i].to; if (e[i].re && dep[v]==-1) { dep[v]=dep[u]+1; q.push(v); } } } return dep[t]!=-1; } int dfs(int u,int flow) { if (u==t || !flow) return flow; int i,v,res,used=0; for (i=cur[u];i!=-1;i=e[i].nxt) { v=e[i].to; cur[u]=i; if (dep[v]==dep[u]+1 && e[i].re) { res=dfs(v,min(flow,e[i].re)); if (res) { used+=res; flow-=res; e[i].re-=res; e[i^1].re+=res; if (!flow) return used; } } } if (flow) dep[u]=-1; return used; } int dinic() { int i,maxflow=0; while (bfs()) { for (i=0;i<=t;i++) cur[i]=lst[i]; maxflow+=dfs(s,inf); } return maxflow; } int main() { int x,y,i,j,k; clear(); memset(mp,0,sizeof(mp)); scanf("%d%d",&n,&m); for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); mp[x][y]=1; } s=0;t=n*n+1; for (i=1;i<=n;i++) for (j=1;j<=n;j++) { if (mp[i][j]) continue; //printf("ij %d %d ",i,j); if ((i+j)&1) { add(s,(i-1)*n+j,1); for (k=0;k<8;k++) { x=i+a[k][0]; y=j+a[k][1]; //printf("xy %d %d %d %d %d ",x,y,k,a[k][0],a[k][1]); if (x<1 || y<1 || x>n || y>n || mp[x][y]) continue; add((i-1)*n+j,(x-1)*n+y,inf); } } else add((i-1)*n+j,t,1); } printf("%d ",n*n-m-dinic()); return 0; }
跑一遍dij，把构成最短路的边加入新图中；再把每个节点分为两个点，之间连一条容量等于该店容量的边。在得到的新图上跑最大流。
（参考了hzwer的代码，他的代码风格真棒啊）
#include<cstdio> #include<cstring> #include<queue> #include<cmath> #define maxn 1005 #define maxm 100005 #define inf (1LL<<60) #define pa pair<int,int> using namespace std; typedef long long ll; int num,lst[maxn],cur[maxn],dep[maxn]; ll dis[505]; int a[maxm],b[maxm],d[maxm]; int s,t,n,m; struct in { int to,nxt; ll w; }e[maxm<<1]; void add(int x,int y,ll w) { e[++num].to=y;e[num].nxt=lst[x];lst[x]=num;e[num].w=w; } void clear() { num=-1; memset(lst,-1,sizeof(lst)); } int dij() { int i,u,v; priority_queue<pa,vector<pa>,greater<pa> >q; for (i=1;i<=n;i++) dis[i]=inf; dis[1]=0; q.push(make_pair(0,1)); while (!q.empty()) { u=q.top().second; q.pop(); for (i=lst[u];i!=-1;i=e[i].nxt) { v=e[i].to; if (dis[u]+e[i].w<dis[v]) { dis[v]=dis[u]+e[i].w; q.push(make_pair(dis[v],v)); } } } } int bfs() { int i,u,v; queue<int>q; while (!q.empty()) q.pop(); memset(dep,-1,sizeof(dep)); dep[s]=0; q.push(s); while (!q.empty()) { u=q.front(); q.pop(); for(i=lst[u];i!=-1;i=e[i].nxt) { v=e[i].to; if (e[i].w && dep[v]==-1) { dep[v]=dep[u]+1; q.push(v); } } } return dep[t]!=-1; } ll dfs(int u,ll flow) { if (u==t || !flow) return flow; int i,v; ll res,used=0; for (i=cur[u];i!=-1;i=e[i].nxt) { v=e[i].to; cur[u]=i; if (dep[v]==dep[u]+1 && e[i].w) { res=dfs(v,min(flow,e[i].w)); if (res) { used+=res; flow-=res; e[i].w-=res; e[i^1].w+=res; if (!flow) return used; } } } if (flow) dep[u]=-1; return used; } int dinic() { int i; ll maxflow=0; while (bfs()) { for (i=1;i<=t;i++) cur[i]=lst[i]; maxflow+=dfs(s,inf); } return maxflow; } int main() { int x,i,j; clear(); scanf("%d%d",&n,&m); for (i=1;i<=m;i++) { scanf("%d%d%d",&a[i],&b[i],&d[i]); add(a[i],b[i],d[i]); add(b[i],a[i],d[i]); } dij(); clear(); for (i=1;i<=m;i++) { if (dis[a[i]]+d[i]==dis[b[i]]) { add(a[i]+n,b[i],inf); add(b[i],a[i]+n,0); } if (dis[b[i]]+d[i]==dis[a[i]]) { add(b[i]+n,a[i],inf); add(a[i],b[i]+n,0); } } for (i=1;i<=n;i++) { scanf("%d",&x); if (i==1 || i==n) add(i,i+n,inf); else add(i,i+n,x); add(i+n,i,0); } s=1;t=2*n; printf("%lld ",dinic()); return 0; }