jerry3128

用户名：jerry3128

访问量：3136

签　名：

等　　级
排　　名	17962
经　　验	757
参赛次数	3
文章发表	3
年　　龄	0
在职情况	学生
学　　校	晃华媛中学
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法提高VIP-高精度乘法（C++代码）----> (FFT)
浏览：1255

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

[竞赛入门]简单的a+b （C++代码）

　　作者: jerry3128　　　　发表时间：2019-12-06 17:07:31 浏览：738　|　评论：0　

原题链接：[竞赛入门]简单的a+b

这道题是我在本站上A的第一道题，那我们直接开始吧：
首先，我们要用到转换的思想，既然这道题跟代数有关，那我们便可以把它转换为图论,如图：
![](/image_editor_upload/20191206050818_68618.jpg)
又因为在题目的数据中并没有负数，那么，显然这个问题就转化为了求源点S到汇点T的最大流，接着就是模板就行了
```
#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;
int getint() {
	int ret=0,flag=1;
	char c=getchar();
	while(c<'0'||c>'9') {
		if(c=='-')flag=-1;
		c=getchar();
	}
	while(c<='9'&&c>='0') {
		ret=(ret<<3)+(ret<<1)+c-'0';
		c=getchar();
	}
	return ret*flag;
}
int n,m;
int S,T;
int cnt,head[100005];
struct edge {
	int ne,v,w,pair;
} e[2000005];
void add(int u,int v,int p) {
	cnt++;
	e[cnt].v=v;
	e[cnt].w=p;
	e[cnt].pair=cnt+1;
	e[cnt].ne=head[u];
	head[u]=cnt;

//	cnt++;
//	e[cnt].v=u;
//	e[cnt].w=0;
//	e[cnt].pair=cnt-1;
//	e[cnt].ne=head[v];
//	head[v]=cnt;
}
int dis[100005],gap[100005];
int DFS(int x,int maxf) {
	if(x==T)return maxf;
	int ret=0;
	for(int i=head[x]; i; i=e[i].ne) {
		int y=e[i].v;
		if(e[i].w&&dis[x]==dis[y]+1) {
			int dlt=DFS(y,min(maxf,e[i].w));
			e[i].w-=dlt;
			e[e[i].pair].w+=dlt;
			ret+=dlt;
			maxf-=dlt;
			if(dis[S]==n||!maxf)return ret;
		}
	}
	if(!(--gap[dis[x]]))dis[S]=n;
	gap[++dis[x]]++;
	return ret;
}
int SAP(int s,int t) {
	int ans=0;
	memset(dis,0,sizeof(dis));
	memset(gap,0,sizeof(gap));
	gap[0]=n;
	while(dis[s]<n)ans+=DFS(s,1<<30);
	return ans;
}
int k[2];
int main() {
	n=2;
	m=2;
	S=1;
	T=2;
	while(scanf("%d%d",&k[0],&k[1])!=EOF) {
		memset(head,0,sizeof(head));
		for(int i=0; i<m; i++) {
			int x=1,y=2,z=k[i];
			add(x,y,z);
			add(y,x,0);
		}
		printf("%d\n",SAP(S,T));
	}
	return 0;
}
```

0.0分

13 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

jerry3128

TA的其他文章

你可能喜欢

C二级辅导-公约公倍（C++代码）

字符逆序（C语言代码）

C二级辅导-等差数列（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

[竞赛入门]简单的a+b （C++代码）

评论区

精彩推荐

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

wu-淘淘的名单（C++代码）

简单的a+b （C语言代码）

【计算球体积】（C语言代码）

C二级辅导-阶乘数列（C语言代码）

川哥的吩咐（C语言代码）

模拟计算器（C语言代码）

jerry3128

TA的其他文章

你可能喜欢

C二级辅导-公约公倍 （C++代码）

字符逆序 （C语言代码）

C二级辅导-等差数列 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

C语言程序设计教程（第三版）课后习题6.1 （C语言代码）

[竞赛入门]简单的a+b （C++代码）

评论区

精彩推荐

printf基础练习2 （C语言代码）

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

C语言程序设计教程（第三版）课后习题6.5 （C语言代码）

wu-淘淘的名单 （C++代码）

简单的a+b （C语言代码）

【计算球体积】 （C语言代码）

C二级辅导-阶乘数列 （C语言代码）

川哥的吩咐 （C语言代码）

模拟计算器 （C语言代码）

C二级辅导-公约公倍（C++代码）

字符逆序（C语言代码）

C二级辅导-等差数列（C语言代码）

　　评论区

wu-淘淘的名单（C++代码）

【计算球体积】（C语言代码）

C二级辅导-阶乘数列（C语言代码）

川哥的吩咐（C语言代码）

模拟计算器（C语言代码）