南京网站制作网页,seo推广百度百科,wordpress实现新闻列表,网上国网app缴费题目链接
点击打开链接
题目解法
考虑可以经停#xff0c;从 i i i 到 j j j 包括维修在内的最短时间#xff0c;这是可以通过 f l o y d O ( n 3 ) floyd\;O(n^3) floydO(n3) 求的 这样我们可以维护出一辆飞机是否可以先运行航班 x x x 再运行航班 y y y#xff0c…题目链接
点击打开链接
题目解法
考虑可以经停从 i i i 到 j j j 包括维修在内的最短时间这是可以通过 f l o y d O ( n 3 ) floyd\;O(n^3) floydO(n3) 求的 这样我们可以维护出一辆飞机是否可以先运行航班 x x x 再运行航班 y y y可以通过上面的预处理维护出来 如果一辆飞机可以先运行航班 x x x 再运行航班 y y y那么我们从 x x x 到 y y y 连一条边 考虑连出的图有何性质显然这是 D A G DAG DAG
考虑简化后的问题在一个 D A G DAG DAG 上有最少的路径覆盖所有的点 这是一个经典问题 考虑拆点把每个点拆成出点和入点有边就从入点往出点连边同时起点向所有入点连边所有出点向终点连边 结论是 D A G DAG DAG 上的最少路径覆盖 总点数 − - − 最大匹配 证明考虑某条路径必有终点且只有终点对应的入点未匹配 反之所以未匹配的点也一定是某条路径的终点那么一个未匹配的点就可以对应一条路径 所以 路径的数目就是未匹配点的数目 需要 路径的数目尽量小所以可得 D A G DAG DAG 上的最少路径覆盖 总点数 − - − 最大匹配 二分图跑 d i n i c dinic dinic 的时间复杂度为 O ( m n ) O(m\sqrt n) O(mn )
时间复杂度为 O ( n 3 m 2 m ) O(n^3m^2\sqrt m) O(n3m2m )
#include bits/stdc.h
#define int long long
using namespace std;
const int N(1100),M(600000),inf(0x3f3f3f3f3f3f3f3f);
struct Node{int x,y,d;
}airl[N];
int n,m,S,T,p[N],t[N][N],d[N][N];
int que[N],hh,tt,dis[N];
int e[M],ne[M],w[M],h[N],cur[N],idx;
inline int read(){int FF0,RR1;char chgetchar();for(;!isdigit(ch);chgetchar()) if(ch-) RR-1;for(;isdigit(ch);chgetchar()) FF(FF1)(FF3)ch-48;return FF*RR;
}
void add(int x,int y,int z){ e[idx]y,w[idx]z,ne[idx]h[x],h[x]idx;}
bool bfs(){memset(dis,0x3f,sizeof(dis));hh0,tt-1,que[tt]S,dis[S]0,cur[S]h[S];while(hhtt){int uque[hh];for(int ih[u];~i;ine[i]){int ve[i];if(w[i]dis[u]1dis[v]) cur[v]h[v],dis[v]dis[u]1,que[tt]v;}}return dis[T]!inf;
}
int find(int u,int limit){if(uT) return limit;int res0;for(int icur[u];~ireslimit;ine[i]){cur[u]i;int ve[i];if(w[i]dis[u]1dis[v]){int tfind(v,min(w[i],limit-res));if(!t) dis[v]-1;rest,w[i]-t,w[i^1]t; }}return res;
}
int dinic(){int tot0,add;while(bfs()) while(addfind(S,inf)) totadd;return tot;
}
signed main(){nread(),mread();for(int i1;in;i) p[i]read();for(int i1;in;i) for(int j1;jn;j) t[i][j]read(); for(int i1;in;i) for(int j1;jn;j) d[i][j]t[i][j]p[i]p[j];for(int i1;in;i) d[i][i]p[i];for(int k1;kn;k) for(int i1;in;i) for(int j1;jn;j)if(i!kk!jj!i) d[i][j]min(d[i][j],d[i][k]-p[k]d[k][j]);for(int i1;im;i) airl[i].xread(),airl[i].yread(),airl[i].dread();memset(h,-1,sizeof(h));S0,T2*m1;for(int i1;im;i) add(S,i,1),add(i,S,0),add(im,T,1),add(T,im,0);for(int i1;im;i) for(int j1;jm;j)if(airl[i].dt[airl[i].x][airl[i].y]d[airl[i].y][airl[j].x]airl[j].d){
// couti jm\n;add(i,jm,1),add(jm,i,0); }printf(%lld,m-dinic());return 0;
}
