h5商城网站开发,wordpress关闭自动保存,wordpress 自测,网站建设设计大作业概念
求两点间的路径中可在同一时间内通过的最大量 EK算法
通过bfs找通路#xff0c;找到后回溯#xff1b;
每确定一条边时#xff0c;同时建立一天反方向的边以用来进行反悔操作#xff08;毕竟一次性找到正确方案的概率太低了#xff09; code
#includebits/st…概念
求两点间的路径中可在同一时间内通过的最大量 EK算法
通过bfs找通路找到后回溯
每确定一条边时同时建立一天反方向的边以用来进行反悔操作毕竟一次性找到正确方案的概率太低了 code
#includebits/stdc.h
#define ll long long
#define inl inline
#define re register
using namespace std;
inl int read() {int sum0,f1;char cgetchar();while(!isdigit(c)) {if(c-) f-1;cgetchar();}while(isdigit(c)) {sum(sum3)(sum1)(c^48);cgetchar();}return sum*f;
}
const int N210;
int dis[10000010],ans,head[N1],tot1,n,m,f[210][210];
struct node{int to,w,nxt;
}e[10000010];
inl void add(int u,int v,int w) {e[tot].tov;e[tot].ww;e[tot].nxthead[u];head[u]tot;e[tot].tou;e[tot].w0;e[tot].nxthead[v];head[v]tot;
}
bool vis[210];
int pre[N];
inl bool bfs() {memset(vis,0,sizeof(vis));queueint q;dis[1]100000000;vis[1]1;q.push(1);while(!q.empty()) {int uq.front();q.pop();for(re int ihead[u];i;ie[i].nxt) {int ve[i].to;if(vis[v]1 || e[i].w0) continue;dis[v]min(dis[u],e[i].w) ;//coutdis[v]endl;pre[v]i;q.push(v);vis[v]1;if(vn) return 1;}}return 0;
}
inl void update() {int un;while(u!1) {int vpre[u] ;e[v].w-dis[n];e[v^1].wdis[n];ue[v^1].to;}ansdis[n];
}
int main() {mread(),nread();for(re int i1;im;i) {int uread(),vread(),wread();if(!f[u][v]) {add(u,v,w);f[u][v]tot;}else{e[f[u][v]-1].ww;}}while(bfs()) {//coutdis[n]endl;update();}coutansendl;return 0;
}
Dinic算法
也是运用bfs将原图进行分层但统计答案时使用dfs,可大大降低时间复杂度 code
#includebits/stdc.h
#define ll long long
#define re register
#define inl inline
using namespace std;
inl int read() {int sum0,f1;char cgetchar();while(!isdigit(c)) {if(c-) f-1;cgetchar();}while(isdigit(c)) {sum(sum3)(sum1)(c^48);cgetchar();}return sum*f;
}
const int N210;
int n,m,x,head[N1],f[210][210],tot1,cur[N*N],ans,d[N];
struct node{int to,nxt,w;
}e[N*N1000];
inl void add(int u,int v,int w) {//cout1endl;e[tot].tov;e[tot].ww;e[tot].nxthead[u];head[u]tot;e[tot].tou;e[tot].w0;e[tot].nxthead[v];head[v]tot;
}
inl bool bfs() {memset(d,0,sizeof(d));queueint q;d[1]1;q.push(1);while(!q.empty()) {int uq.front() ;q.pop();for(re int ihead[u];i;ie[i].nxt) {int ve[i].to;if(!d[v] e[i].w) {d[v]d[u]1;q.push(v);if(vn) return 1;}}}return 0;
}
inl int dfs(int u,int mf) {if(un) return mf;int tmp0;for(int icur[u];i;ie[i].nxt) {cur[u]i;int ve[i].to;if(d[v]d[u]1 e[i].w) {int tmp1dfs(v,min(mf,e[i].w));e[i].w-tmp1;e[i^1].wtmp1;tmptmp1;mf-tmp1;if(!mf) break;}}if(!tmp) d[u]0;return tmp;
}
inl void dinic() {while(bfs()) {memcpy(cur,head,sizeof head);ansdfs(1,100000000);}
}
int main() {nread();mread();xread();//coutn m xendl;for(re int i1;im;i) {int uread(),vread(),wread();if(!f[u][v]) {add(u,v,w);f[u][v]tot;}else{e[f[u][v]-1].ww;}}dinic();if(!ans) {puts(Orz Ni Jinan Saint Cow!);}else {int px/ans;if(p*ansx) {p;}printf(%d %d\n,ans,p);}return 0;
}
