首页 > 其他分享 >二分图笔记

二分图笔记

时间:2023-08-21 15:45:45浏览次数:42  
标签:二分 匹配 标记 int 笔记 bool match

二分图定义

二分图是一张无向图,可以分成 \(2\) 个集合 \(A\) 和 \(B\)。在同一个集合中的点没有边相连。

二分图判定

当且仅当图中不存在奇数环时,该图为二分图。

证明:反证法,构造一个奇数环。容易发现无论如何都不可能使相邻 \(2\) 点分到 \(2\) 个集合。

那么很容易想到一个判定二分图的方法:dfs染色法。

可以用 \(2\) 种颜色给图上的点进行染色。有边相连的点应该染成相反的颜色。如果在染色过程中出现冲突,则此图不是二分图。

示例代码:

bool dfs(int x,int c){
	clr[x]=c;
	for(int i=0;i<to[x].size();i++){
		int v=to[x][i];
		if(!vst[v]){
			if(!dfs(v,3-c))  return 0;
		}
		else{
			if(clr[v]==clr[x])  return 0;
		}
	}
	return 1;
}

易证该算法的时间复杂度是 \(\Theta(n)\)。

例题1 P1525 关押罪犯。对于本题,我们希望分配到同一个监狱里的罪犯的最大仇恨值(即边权值)最小化,容易想到二分答案。

判定:存在一种方案,使得冲突影响力不超过mid。

该判定方法显然符合单调性(mid较小的方案,对于更大的mid一定可行)。

因此,如果我们忽略所有边权值小于mid的边后形成的图进行判定二分图成立,那么方案可行,继续二分mid,直到找到答案。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,maxx,ans;
vector<int> t[20009],a[20009];
int vst[20009];
bool Big=1;
void dfs(int u,int color,int num){
	if(!Big)  return ;
	vst[u]=color;
	for(int i=0;i<t[u].size();i++){
		if(a[u][i]>num){
			if(!vst[t[u][i]])  dfs(t[u][i],3-color,num);
	     	else if(vst[t[u][i]]==color)  Big=0;
		}
		
	}
	return ;
}
bool ok(int num){
	Big=1;
	for(int i=1;i<=n;i++) vst[i]=0;
	for(int i=1;i<=n&&Big;i++){
		if(!vst[i])  dfs(i,1,num);
	}
	if(Big)  return 1;
	return 0;
}
int main(){
//	freopen("prison.in","r",stdin);
//	freopen("prison.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int pa,b,c;
		cin>>pa>>b>>c;
		t[pa].push_back(b);
		a[pa].push_back(c);
		t[b].push_back(pa);
		a[b].push_back(c);
		maxx=max(c,maxx);
	}
	int left=0,right=maxx,mid;
	ans=right;
	while(left<=right){
		mid=(left+right)/2;
		if(ok(mid)) 
		{
			if(ans>mid) ans=mid;
			right=mid-1;
		 } 
		else left=mid+1;
	}
	cout<<ans;
	return 0;
}

二分图匹配

匹配是一个边的集合 \(E\) ,满足任意 \(2\) 条边之间没有公共端点。而最大匹配即为二分图中,包含边数最多的一组匹配(\(max|E|\))。

首先了解以下几个概念:

匹配边:\((x,y)∈E\),反之称为非匹配边。

匹配点:如果 \((x,y)∈E\),则 \(x\) 和 \(y\) 为匹配点。反之 \(x\) 和 \(y\) 为非匹配点。

交错路:一条非匹配边和匹配边交替经过的路径。

增广路:一边的非匹配点到另一边的非匹配点的交错路。

寻找二分图最大匹配的算法为匈牙利算法,算法步骤:

1.设 \(S\) 为空集,所有边都是非匹配边

2.寻找增广路path,如果找到,把所有路径上的边的匹配状态取反,得到一个更大的匹配。

3.重复第 \(2\) 步,直到图中不存在增广路。

寻找增广路:递归地从每个点 \(x\) 出发递归 \(y\) 寻找增广路。如果找到,一边回溯一边修改匹配状态。\(match[x]=y\)

要么 \(y\) 没有匹配点,要么 \(y\) 有匹配点,但是从 \(y\) 的匹配点出发递归去找增广路,可以找到。

dfs的时间复杂度为 \(\Theta(n)\),匈牙利算法的时间复杂度为 \(\Theta(n^2)\)

示例代码:

#include<bits/stdc++.h>
using namespace std;
const int N=100009;
int n,m,ans,match[N];
vector<int> to[N];
bool vst[N];
bool dfs(int x){
	for(int i=0;i<to[x].size();i++){
		int y=to[x][i];
		if(vst[y])  continue;
		if(!match[y]||dfs(match[y])){
			match[y]=x;
			return 1;
		}
	}
	return 0;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;
		cin>>x>>y;
		to[x].push_back(y);
		to[y].push_back(x);
	}
	for(int i=1;i<=n;i++){
		memset(vst,0,sizeof(vst));  //已经经过的点也要重新判断,每次都要清空vst数组
		if(dfs(i))  ans++; 
	}
	cout<<ans;
	return 0;
}

例题1 T270574 棋盘覆盖。本题主要考察的是二分图建模,建模时要满足以下 \(2\) 个要求。

  1. 节点可以分成 \(2\) 个集合,集合内部的点没有边相连。
  2. 每个节点只能有 \(1\) 条边(匹配边)。

该题要求任意 \(2\) 张骨牌都不会重叠,即每个格子只能被 \(1\) 张骨牌覆盖,而每张骨牌可以覆盖 \(2\) 个格子。把骨牌看作边,格子看作点。

考虑把每个没有被禁止的格子分为 \(2\) 个不同的集合。

将格子像国际象棋棋盘交叉黑白染色,可以划分为 \(2\) 个不重叠的集合。黑色格子的行号+列号为奇数,白色格子的行号+列号为偶数。容易发现每个骨牌必然覆盖一个黑色格子和一个白色格子。

要求所需的最大骨牌数量,即求二分图最大匹配,用匈牙利算法。

时间复杂度为 \(\Theta(n^3)\)

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,t,ans;
int match[10009];
int to[2009][2009];
bool vst[10009];
int tot,To[400009],head[400009],nxt[400009];
void add(int u,int v){
	To[++tot]=v;
	nxt[tot]=head[u];
	head[u]=tot;
}
bool ok(int x){
	for(int i=head[x];i;i=nxt[i]){
		int y=To[i];
		if(vst[y])  continue;
		vst[y]=1;
		if(!match[y]||ok(match[y])){
			match[y]=x;
			return 1;
		}
	}
	return 0;
}
int main(){
	cin>>n>>t;
	for(int i=1;i<=t;i++){
		int x,y;
		cin>>x>>y;
		to[x][y]=1;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<n;j++){
			if(to[i][j]||to[i][j+1])  continue;
			int u=(i-1)*n+j,v=u+1;
			add(u,v);
			add(v,u); 
		}
	}
	for(int i=1;i<n;i++){
		for(int j=1;j<=n;j++){
			if(to[i][j]||to[i+1][j])  continue;
			int u=(i-1)*n+j,v=i*n+j;
			add(u,v);
			add(v,u); 
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(to[i][j]||(i+j)%2)  continue;
			int u=(i-1)*n+j;
			memset(vst,0,sizeof(vst));
			ans+=ok(u);
		}
	}
	cout<<ans;
	return 0;
}

例题2 T270575 車的放置。首先显然每行每列只能有 \(1\) 个車。考虑构造行和列 \(2\) 个集合,車为连边,那么車的数量就是行和列的最大匹配边数。但要求有 \(T\) 个点不能放置,禁止点 \((i,j)\) 即行 \(i\) 和列 \(j\) 不能有连边。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,t,ans;
int match[209];
int to[209][209];
bool vst[209];
bool ok(int x){
	for(int i=1;i<=m;i++){
		if(!vst[i]&&!to[x][i]){
			vst[i]=1;
			if(!match[i]||ok(match[i])){
				match[i]=x;
				return 1;
			}
		}
	}
	return 0;
}
int main(){
	cin>>n>>m>>t;
	for(int i=1;i<=t;i++){
		int x,y;
		cin>>x>>y;
		to[x][y]=1;
	}
	for(int i=1;i<=n;i++){
		memset(vst,0,sizeof(vst));
		ans+=ok(i);
	}
	cout<<ans<<endl;
	return 0;
}

例题3 T311481 导弹防御塔。题目要求“最大时间最小化”,因此显然符合二分答案的单调性,考虑二分答案来解决此问题。

二分图的多重匹配,即给出一个包含 \(n\) 个左部节点和 \(m\) 个右部节点的二分图,从中选出尽量多的边,使第 \(i\) 个左部节点,最多和 \(x\) 条选出的边相连,使第 \(j\) 个右部节点最多 \(y\) 条选出的边相连。

当 \(x=y=1\) 时,就是二分图的最大匹配。

解决多重匹配有以下几种方案:

  1. 拆点:即把左部每个点拆成至多 \(x\) 个点,右部的点拆成至多 \(y\) 个点,套用最大匹配即可。
  2. 网络流,在此不多赘述。

对于本题,对于 \(m\) 个入侵者和 \(n\) 枚导弹 \(2\) 个集合,易证对于mid的时间,最多发射出 \(p=\frac{mid+T_2}{T_1+T_2}\) 枚导弹,即把 \(1\) 枚导弹拆成 \(p\) 枚导弹。但注意导弹在空中飞行也有时间,不一定在 \(mid\) 时间前发射的导弹就一定能在时间限制前摧毁目标。

因此本题思路为 二分+拆点建图+二分图最大匹配。时间复杂度为 \(\Theta(mnp+n^2)\)

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const double eps=1e-9;
int n,m,match[4009];
double t1,t2,v,dist[59][59];
PII a[59],b[59];
bool vst[4009];
vector<int> to[59];
double get_dist(int i,int j){
	double x=a[i].first-b[j].first;
	double y=a[i].second-b[j].second;
	return sqrt(x*x+y*y);
}
bool find(int x){
	for(int i=0;i<to[x].size();i++){
		int y=to[x][i];
		if(vst[y])  continue;
		vst[y]=1;
		if(!match[y]||find(match[y])){
			match[y]=x;
			return 1;
		}
	}
	return 0;
}
bool check(double mid){
	memset(match,0,sizeof(match));
	for(int i=1;i<=m;i++){
		memset(vst,0,sizeof(vst));
		if(!find(i))  return 0;
	}
	return 1;
}
int main(){
	cin>>n>>m>>t1>>t2>>v;
	t1/=60;
	for(int i=1;i<=m;i++){
		cin>>a[i].first>>a[i].second;
	}
	for(int i=1;i<=n;i++){
		cin>>b[i].first>>b[i].second;
	}
	for(int i=1;i<=m;i++){
		for(int j=1;j<=n;j++){
			dist[i][j]=get_dist(i,j);
		}
	}
	double l=0,r=1e9;
	while(r-l>eps){
		double mid=(l+r)/2;
		int p=(mid+t2)/(t1+t2);
		p=min(p,m);
		for(int i=1;i<=m;i++){
			to[i].clear();
			for(int j=1;j<=n;j++){
				for(int k=1;k<=p;k++){
					if(k*t1+(k-1)*t2+dist[i][j]/v<mid-eps){
						to[i].push_back((j-1)*p+k);
					}
				}
			}
		}
		if(check(mid))  r=mid;
		else  l=mid;
	}
	cout<<fixed<<setprecision(6)<<r;
	return 0;
}



二分图的最小点覆盖

对于二分图,最小点覆盖的点数等价于二分图的最大匹配包含的边数,即为König定理。

证明:

设二分图最小点覆盖的点数为 \(n\) ,最大匹配书边数为 \(m\),证明 \(n=m\)

1.证明 \(n≥m\)

因为所有的 \(m\) 条匹配边之间没有公共点。而最小点覆盖想要覆盖这些匹配边,至少也得要 \(m\) 个点才能完全覆盖。

所以 \(n≥m\) 显然成立。

2.证明 \(n=m\) 可以取到

构造方案:恰好取了 \(m\) 个点,且这 \(m\) 个点能够将所有的边覆盖掉。

构造方式:

  1. 求出最大匹配,有 \(m\) 条匹配边。

  2. 从左部每个非匹配点出发,跑一遍增广路径,将路径上的所有点标记(这里增广路径一定不会成功,因为成功的话就不是最大匹配了,最大匹配后没有增广路径)。

  3. 选出左边所有未被标记的点和右边所有被标记的点。

那么如何证明这种构造方式得到的点数是 \(m\):

\((1)\) 明确有以下三个性质:

1.左边所有的非匹配点一定都被标记(因为每次构造是从左边非匹配点出发的,是起点)

2.右边所有的非匹配点一定没有被标记(因为右边非匹配点被标记的话,就会形成增广路径)

3.对于每个匹配边,左右两点要么同时被标记,要么同时不被标记(因为左边的匹配点一定是从右边某个匹配点过来的)。

\((2)\) 我们选择的是左边所有未被标记的点,则由性质 \(1\) 可知这些点一定是匹配点。

我们选择的是右边所有被标记的点,则由性质 \(2\) 可知这些点一定是匹配点。

所以我们选择的所有点一定是匹配边上的点。

\((3)\) 而对于每个匹配边,左右要么同时被标记,要么同时不被标记。

同时被标记的匹配边,由于我们选择了右边所有被标记的点,所以这些匹配边我们全选了。

同时不被标记的匹配边,由于我们选择了左边所有不被标记的点,所以这些匹配边我们全选了。

由 \((2),(3)\) 可知,我们的选择是所有的 \(m\) 条匹配边,且每个匹配边我们只会选择左,或者右边一个点。一共 \(m\) 个点。

所以这种构造方式得到的点数是 \(m\)。

接着证明这种构造方式覆盖了所有的边。

首先匹配边我们已知全部覆盖,因为由上面的证明我们可以知道 \(m\) 条边匹配边都被选了。

剩下的非匹配边有两种情况:

\((1)\) 左边的非匹配点连接右边的匹配点:

因为左边非匹配点我们都标记了,从这个非匹配点出发走增广路径,所以这样的边,它右边的匹配点也一定被标记,而右边被标记的点会被我们选择,所以我们选择的点会覆盖这样的边。

\((2)\) 左边匹配点连接右边非匹配点:

如果左边匹配点被标记,且有这样的一条边,那么走下去,右边的这个非匹配点也会被标记。与性质 \(2\) 右边所有非匹配点都不会被标记矛盾(存在增广路径)。

所以这样的边的左边匹配点一定不会被标记,那么它会被选中,所以这样的边也会被覆盖。

由 \((1),(2)\) 可知这种构造方式覆盖了所有的边。

综上,这种构造方式可以构造出用 \(m\) 个点覆盖所有的边的情况=最大匹配数,证明了等号可以取得。

所以 \(n=m\),即最小点覆盖数=最大匹配数。

二分图最小点覆盖建模前提:每条边 \(2\) 个端点,并且每条边至少选择 \(1\) 个端点。

例题1 T311483 机器任务。把两台机器 \(A,B\) 看作 \(2\) 个集合,考虑二分图最小点覆盖的特点:每一条边的 \(2\) 个结点至少要选择 \(1\) 个,代入此题就是每个任务必须在 \(2\) 台机器中选择一台,要么用 \(a_i\) 模式,要么用 \(b_i\) 模式。因此本题答案显然为二分图最小点覆盖。

注意因为机器初始时为 \(0\) ,因此要把端点有 \(0\) 的点排除在外(不影响重启次数)。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k;
vector<int> to[100009];
int match[109];
bool vst[109];
bool hungary(int x){
	for(int i=0;i<to[x].size();i++){
		int y=to[x][i];
		if(vst[y])  continue;
		vst[y]=1;
		if(!match[y]||hungary(match[y])){
			match[y]=x;
			return 1;
		}
	}
	return 0;
}
int main(){
	while(cin>>n){
		if(n==0)  break;
		cin>>m>>k;
		for(int i=0;i<=n;i++)  to[i].clear();
		for(int i=1;i<=k;i++){
			int j,a,b;
			cin>>j>>a>>b;
			if(a==0||b==0)  continue;
			to[a].push_back(b);
		}
		int ans=0;
		for(int i=0;i<n;i++){
			memset(vst,0,sizeof(vst));
			if(hungary(i))  ans++;
		}
		cout<<ans<<endl;
	} 
	return 0;
}

例题2 T311743 泥泞的区域。对于任意一个泥泞的格子 \((i,j)\),要么是被横着盖,要么是被竖着盖,满足二分图最小点覆盖的建模前提。接下来将每一个泥泞的格子编横块号和列块号,将两个编号连起来,运行二分图最小点覆盖即可。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
int n,m;
char a[59][59];
int match[2509];
int b[59][59],c[59][59];
bool vst[2509];
vector<int> to[2509];
bool hungary(int x){
	for(int i=0;i<to[x].size();i++){
		int y=to[x][i];
		if(vst[y])  continue;
		vst[y]=1;
		if(!match[y]||hungary(match[y])){
			match[y]=x;
			return 1;
		}
	}
	return 0;
}
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++)  cin>>a[i][j];
	}
	int cnt1=1,cnt2=1;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='*')  b[i][j]=cnt1;
			else  cnt1++;
		}
		cnt1++;
	}
	for(int j=1;j<=m;j++){
		for(int i=1;i<=n;i++){
			if(a[i][j]=='*')  c[i][j]=cnt2;
			else  cnt2++;
		}
		cnt2++;
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(a[i][j]=='*'){
				to[b[i][j]].push_back(c[i][j]);
			}
		}
	}
	int ans=0;
	for(int i=1;i<=cnt1;i++){
		memset(vst,0,sizeof(vst));
		if(hungary(i))  ans++;
	}
	cout<<ans;
	return 0;
}

二分图最大独立集

独立集:一个点集,其中任意 \(2\) 点之间都没有边相连。

最大独立集:点数最多的独立集。

二分图最大独立集 \(=\) \(n\) \(-\) 二分图最小点覆盖(最大匹配)

证明:求最大独立集的过程可以看作是删去数量最少的点和它们的连边,使得所有边都被删除,剩下的点就是最大独立集。而删去的点集即为最小点覆盖,因此二分图最大独立集和二分图最小点覆盖互为补集。

例题1 T311485 骑士放置。将棋盘交叉黑白染色,观察发现,当骑士在黑色格子内时,能攻击的点必定是白色格子,反之必定是黑色格子。满足二分图“同一个集合内的点必定没有连边”。连边意味着能攻击到,而本题要求的是最多放置多少个不能攻击的骑士,因此选出来的点不能有连边,即求二分图最大独立集。

AC代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
typedef pair<int,int> PII;
int cx[8]={2,2,-1,-1,1,1,-2,-2};
int cy[8]={-1,1,-2,2,-2,2,-1,1};
int n,m,t;
bool vst[109][109];
PII match[109][109];
int unable[109][109];
bool hungary(int x,int y){
	for(int i=0;i<8;i++){
		int nx=x+cx[i],ny=y+cy[i];
		if(nx<1||nx>n||ny<1||ny>m||unable[nx][ny]||vst[nx][ny])  continue;
		vst[nx][ny]=1;
		if((match[nx][ny].first==0&&match[nx][ny].second==0)||hungary(match[nx][ny].first,match[nx][ny].second)){
			match[nx][ny]=make_pair(x,y);
			return 1;
		}
	}
	return 0;
}
int main(){
	cin>>n>>m>>t;
	for(int i=1;i<=t;i++){
		int x,y;
		cin>>x>>y;
		unable[x][y]=1;
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			memset(vst,0,sizeof(vst));
			if(unable[i][j]||((i+j)&1))  continue;  
			if(hungary(i,j))  ans++;
		}
	}
	cout<<n*m-ans-t;
	return 0;
}

标签:二分,匹配,标记,int,笔记,bool,match
From: https://www.cnblogs.com/11jiang08/p/17646173.html

相关文章

  • 8.21 随笔记录
    高速CAN和低速CAN的区别高速CAN和低速CAN的物理层电气特性不一样,因此不能互相连接高速CAN主要应用于发动机、变速箱等实时性要求高的场合低速CAN主要应用于车身控制系统等可靠性要求高的场合CAN_H和CAN_L任意一根导线损坏,高速CAN收发失效,而低速CAN收有效,因此低速CAN的可靠性......
  • 学习笔记411—【词向量基础】:one-hot
    【词向量基础】:one-hot词向量(wordvector),也叫词嵌入(wordembedding),是一种词表征形式,将词从符号形式映射为向量形式,渐渐演变成了一种知识表示的方法。将词语从符号表示形式转换为了向量表示形式,方便了机器对自然语言的计算,因此,词向量几乎成为了所有自然语言处理和理解的下游任务的......
  • 概率与数学期望笔记
    概率论样本点:一个随机试验的某种可能的结果。样本空间\(Ω\):所有可能结果构成的集合随机事件\(A\):在一个给定的样本空间中,样本空间的子集,即由多个样本点构成的集合。随机变量\(P(A)\):把样本点映射为实数的函数,分为离散型、连续型。离散型随机变量的取值为有限或实数。我们......
  • halcon 笔记 算子
    1.read_image()*读取图像11.pngread_image(Image,‘11.png’)   *计算图像的通道数count_channels(Image,Num)*循环读取每个通道的图像forindex:=1toNumby1*获取多通道图像中指定的通道图像access_channel(Image,channel,index)endfor*分解通道decompos......
  • 8.21集训笔记
    上午P1789【Mc生存】插火把点击查看代码#include<bits/stdc++.h>usingnamespacestd;constintN=110;boola[N][N];intn,m,k,x,y;intdx[]={-1,-1,1,1};intdy[]={-1,1,-1,1};boolin(intx,inty){return(x>=1&&x<=n&&y>=1&......
  • 【刷题笔记】27. Remove Element
    题目Givenanarraynumsandavalueval,removeallinstancesofthatvaluein-placeandreturnthenewlength.Donotallocateextraspaceforanotherarray,youmustdothisbymodifyingtheinputarrayin-placewithO(1)extramemory.Theorderofeleme......
  • javascript学习笔记day4
    今天重点学习了数组,老实说学过了c#和python的数组,但是今天重新接触js的数字还是有很多要重新学习的,下面是今天的笔记查询条件五个以上时,switch的效果比iflese高两倍以上.letarr=[]声明数组letarr=newArray(1,2,3,4)声明数组修改数组letarr=['a','b','c']for(letinde......
  • Markdown学习笔记
    Markdown学习标题两个井号加空格三级标题四级标题字体Hello,World!左右一颗*Hello,World!左右两颗*Hello,World!左右三颗*Hello,World!左右来两个~引用狂神说单箭头 分割线图片感叹号+方括号内放图片的命名+圆括号放图片的本地或网络地址超链接点击跳转......
  • python刷小红书流量(小眼睛笔记访问量),metrics_report接口,原理及代码,以及x-s签名验证202
    一、什么是小眼睛笔记访问量 如下图所示,为笔记访问量。二、小眼睛笔记访问量接口1、urlhttps://edith.xiaohongshu.com/api/sns/web/v1/note/metrics_report2、payloaddata={"note_id":note_id,"note_type":note_type,"report_type":1,......
  • 【算法】二分查找实现过程
    1、二分查找的基本思想是,要查找的值和整个数组序列的中间值做比较,确认该值在其中一半里,只要在数组序列一半中继续搜索。2、采用二分查找方法的前提条件是数组或线性表中元素必须按照大小有序排列。代码如下,intmain(){ intarr[]={1,2,3,4,5,6,7,8,9,10}; intk=7......