江门网站推广排名,360建筑网官网市场价,wordpress修改code标签,wordpress哪个版本 最快题干#xff1a;
如题#xff0c;给出一个网络图#xff0c;以及其源点和汇点#xff0c;求出其网络最大流。
输入输出格式
输入格式#xff1a; 第一行包含四个正整数N、M、S、T#xff0c;分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含…题干
如题给出一个网络图以及其源点和汇点求出其网络最大流。
输入输出格式
输入格式 第一行包含四个正整数N、M、S、T分别表示点的个数、有向边的个数、源点序号、汇点序号。
接下来M行每行包含三个正整数ui、vi、wi表示第i条有向边从ui出发到达vi边权为wi即该边最大流量为wi 输出格式 一行包含一个正整数即为该网络的最大流。 输入输出样例
输入样例#1 复制
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 40
输出样例#1 复制
50
解题报告 RT。
AC代码
#includecstring
#includecstdio
#includealgorithm
#includeiostream
using namespace std;
int n,m;
int tot;
struct Edge {int to,ne,w;
} e[100005 * 2];
int head[10005];
int st,ed;
int dis[10050],q[10005];//一共多少个点跑bfsdis数组和q数组就开多大。
void add(int u,int v,int w) {e[tot].tov;e[tot].ww;e[tot].nehead[u];head[u]tot;
}
bool bfs(int st,int ed) {memset(dis,-1,sizeof(dis));int front0,tail0;q[tail]st;dis[st]0;while(fronttail) {int cur q[front];front;for(int i head[cur]; i!-1; i e[i].ne) {if(e[i].wdis[e[i].to]0) {q[tail]e[i].to;dis[e[i].to]dis[cur]1;}}}if(dis[ed]-1) return 0;return 1;
}
int dfs(int cur,int f) {if(cured) return f;int w,flow0;for(int i head[cur]; i!-1; i e[i].ne) { if(e[i].wdis[e[i].to]dis[cur]1) {wf-flow;wdfs(e[i].to,min(w,e[i].w));e[i].w-w;e[i^1].ww;floww;if(flowf) return f;} }if(!flow) dis[cur]-1;return flow;
}
int dinic() {int ans 0;while(bfs(st,ed)) ansdfs(st,0x7fffffff);return ans;
}
int main() {cinnmsted;tot1;for(int i 1; in; i) head[i] -1;for(int a,b,c,i 1; im; i) {scanf(%d%d%d,a,b,c);add(a,b,c);add(b,a,0);} printf(%d\n,dinic()); return 0;
}
得出结论如果是^1的话那就必须tot1然后存边的时候tot这样。
但是要是i和i1的话那就tot1或者tot2都可以了。
