题目描述
给定一个二分图，其中左半部包含n1个点（编号1~n1），右半部包含n2个点（编号1~n2），二分图共包含m条边。
数据保证任意一条边的两个端点都不可能在同一部分中。
请你求出二分图的最大匹配数。
算法：匈牙利求二分图的最大匹配
时间复杂度：$O(N·M)$
C++代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=510,M=100010;
int h[N],e[M],ne[M],idx;
int n1,n2,m;
int match[N];
bool st[N];
int cnt;
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool find(int x)
{
for(int i=h[x];~i;i=ne[i]){
int j=e[i];
if(!st[j]){
st[j]=true;
if(!match[j] || find(match[j])){
match[j]=x;
return true;
}
}
}
return false;
}
int main()
{
cin>>n1>>n2>>m;
memset(h,-1,sizeof h);
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
add(a,b);
}
int res=0;
for(int i=1;i<=n1;i++){
memset(st,false,sizeof st);
if(find(i))cnt++;
}
cout<<cnt<<endl;
return 0;
}
(暴力枚举)
将环拆成链的方法：将字符串复制一遍拼接在原字符串后面
C++ 代码
#include<iostream>
using namespace std;
const int N=710;
char s[N];
int get(char ch)
{
if(ch=='b') return 1;
else if(ch=='r') return 2;
else return 0;
}
int main()
{
int n;
cin>>n>>s;
for(int i=0;i<n;i++) s[i+n]=s[i];
int ans=0;
for(int i=0;i<n;i++)
{
int l=i,r=i+n-1;
int left=0,right=0,cnt=0;
while(l<=r&&(s[l]=='w'||(get(s[l])|left)!=3)) //位运算优先级很低 记得加括号
{
left|=get(s[l]);
l++;
cnt++;
}
while(l<=r&&(s[r]=='w'||(get(s[r])|right)!=3))
{
right|=get(s[r]);
r--;
cnt++;
}
ans=max(ans,cnt);
}
cout<<ans;
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
题目描述
一个数n可以进行两种变换:
1.除以一个非自身的约数
2.加上1
输出能使数字n变成1的最小变换次数
输入
- 第一行一个整数 $t$, $ 1 <= t <= 1000 $, 表示测试数据数量
- 接下来的$t$行，每行包含一个整数 $n$, $ 1 <= n <= 10^9$
输出
共$t$行，每一行输出把$n$变成$1$的最小变换次数
样例
输入:
6
1
2
3
4
6
9
输出:
0
1
2
2
2
3
解释:
1
2→1
3→2→1
4→2→1
6→2→1
9→3→2→1
算法1
(数学) $O(1)$
- 将$n$分成以下几种情况讨论
- $n == 1$, $ ans = 0 $.
- $n == 2$, $ ans = 1 $, 因为 $2→1$
- $n == 3$, $ ans = 2 $, 因为 $3→2→1$
- $n > 3$:
- 如果 $3|n$, 那么 $ans = 3$, 因为 $n→3→2→1$
- 如果 $2|n$, 那么 $ans = 2$, 因为 $n→2→1$
- 如果 $ n mod 2 == 1$, 那么 $ ans = 3$, 因为总有 $n→ (n + 1) → 2→1$ 且 $3|n$的情况不优于这种情况。
- 因此分情况讨论$n$的类型即可。
时间复杂度
- 只需要判断$n$是否是 $1$, $2$, $3$, 或其$奇偶性$，因此时间复杂度为 $O(1)$.
C++ 代码
int T;
cin >> T;
while(T --){
int x;
cin >> x;
if (x == 1) cout << 0 << endl;
else if (x == 2) cout << 1 << endl;
else if (x == 3) cout << 2 << endl;
else if (x % 2 == 0) cout << 2 <<endl;
else cout << 3 << endl;
}
静态链表重点分析
相信很多只学过动态链表的同学刚接触到静态链表的时候会一脸懵，但其实只要将两种链表对比来看就很清晰了：
动态链表的逻辑结构与实际结构是一致的；
静态链表的逻辑结构与实际结构是不一致的；
动态链表是利用指针将一个个节点连接起来，而静态链表是用两个数组来实现的；
也即是说，对于动态链表，只要得到其头节点的指针p，按照p = p->next即可进行遍历；
但对于静态链表，如果按照for(int i = 0; i < n; i ++)这样通用的方式去遍历e[N]数组，是无法得到正确的序列的。
对于静态链表的正确遍历方式是，由i = head进入，读取e[i]作为value，ne[i]作为next，直到 i = -1停止；
index作为实际结构的标识，标志着数组存储邻接表的实际索引。
C++ 代码
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int head, e[N], ne[N], index;//最好不要命名为index，会与string库中的函数冲突
//index实际上是标识头节点的指针，即头节点的下标索引
void init()//初始化
{
head = -1;// -1相当于动态链表里的NULL
index = 0;//两个数组从0开始存储
}
void insert_head(int x)//插到头节点后
{
e[index] = x;
ne[index] = head;
head = index;
index ++ ;
}
void delete_node(int k)
{
ne[k - 1] = ne[ne[k - 1]];
//注意这里不能按照动态链表的思想写成ne[k - 1] = ne[k]
//因为ne[k]是ne[k - 1]实际上的下一个位置 而不是逻辑上的下一个位置
}
void insert_node(int k, int x)
{
e[index] = x;
ne[index] = ne[k - 1];
ne[k - 1] = index;
index ++ ;
}
int main()
{
init();
int m;
cin >> m;
for(int i = 0; i < m; i ++ )
{
char button;
int x, k;
cin >> button;
if(button == 'H')
{
cin >> x;
insert_head(x);
}
else if(button == 'D')
{
cin >> k;
if(!k) head = ne[head];
else delete_node(k);
}
else if(button == 'I')
{
cin >> k >> x;
insert_node(k, x);
}
}
for(int i = head; i != -1; i = ne[i])
{
cout << e[i] << ' ';
}
return 0;
}
题目描述
给定一个n个点m条边的无向图，图中可能存在重边和自环。
请你判断这个图是否是二分图。
算法：深度优先搜索
时间复杂度：O(N+M)
C++代码
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010,M=N*2;
int h[N],e[M],ne[M],idx;
int n,m;
bool st[N];
int color[N];
void add(int a,int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
bool dfs(int u,int c)
{
color[u]=c;
for(int i=h[u];~i;i=ne[i]){
int j=e[i];
if(color[j]==-1){
if(!dfs(j,!c))
return false;
}
else if(color[j]==c)return false;
}
return true;
}
int main()
{
scanf("%d%d",&n,&m);
memset(h,-1,sizeof h);
memset(color,-1,sizeof color);
for(int i=0;i<m;i++){
int a,b;
scanf("%d%d",&a,&b);
add(a,b);add(b,a);
}
bool success=true;
for(int i=1;i<=n;i++){
if(color[i]==-1){
if(!dfs(i,0)){
success=false;
break;
}
}
}
if(success)cout<<"Yes"<<endl;
else cout<<"No"<<endl;
return 0;
}
分享
数组模拟邻接表
这篇分享记录一下我对数组模拟邻接表的理解。
首先假设我们有n个点(n <= N)，m条边(m <= M)。
我们可以想一下对于任意一个结点u, 需要记录邻边的哪些信息。
这些信息应该包括这条邻边的终点，权重，以及下一条邻边的编号。
所以我们可以定义一个struct来表示邻边:
struct Edge // 注意这里不需要记录边的起点
{
int eid; // 该条边的编号
int e; // 该条边的终点
int w; // 该条边的权重
int nxt; // 下一条邻边的编号
};
如果我们用上面的数组来记录邻边的信息，那么我们只需要定义如下变量来表示邻接表：
// 注意N和M的区别
int h[N];
Edge edges[M];
int eidx;
由于每条边都记录了下一条边的编号，这样我们只要把每个结点的第一条邻边的编号记录在h数组，我们就可以遍历它的每一条邻边了。
如果我们把Edge里的信息分开存到不同数组里，那么我们可以得到平时我们看到的变量定义：
// 注意N和M的区别
int h[N];
int e[M], w[M], nxt[M]; // 注意这些数组的下标表示了边的编号
int eidx;
这里每个数组的下标的含义不一样。
关键的事情说三遍：h数组的下标为结点的编号，e,w,nxt数组的下标为边的编号，eidx为边的编号
关键的事情说三遍：h数组的下标为结点的编号，e,w,nxt数组的下标为边的编号，eidx为边的编号
关键的事情说三遍：h数组的下标为结点的编号，e,w,nxt数组的下标为边的编号，eidx为边的编号
如果理解了以上，下面就很好理解了。
有向图的邻接表存储就是对于每个点 u 对应一个头节点h[u]，记录第一条邻边的编号。
e, w, nxt数组的编号和建图的顺序有关，对于某一个点u, 它的所有邻边的编号不一定是连续的。
nxt[eidx]=h[u]; h[u]=eidx; 这个操作就是把新建的边插入表头。(先把新建的边的next指向现在队头的next，然后更新队头的next）
然后再eidx++, 给下一次建边使用
下边用图模拟一下加入四条边的过程
1. 初始状态
2. 加完第一条边(1,2,9)之后
3. 加完第二条边(2,4,1)之后
4. 加完第三条边(1,3,3)之后
这里可以看到后加入的边，反而在邻接表的最前面
5. 加完第四条边(3,4,5)之后
最后是代码及注释
const int N = 1010, M = 1010;
int h[N], e[M], w[M], nxt[M], eidx;
void add(int u, int v, int weight) // 添加有向边 u->v, 权重为weight
{
e[eidx] = v; // 记录边的终点
w[eidx] = weight; // 记录边的权重
nxt[eidx] = h[u]; // 将下一条边指向结点u此时的第一条边
h[u] = eidx; // 将结点u的第一条边的编号改为此时的eidx
eidx++; // 递增边的编号edix, 为将来使用
}
void iterate(int u) // 遍历结点u的所有邻边
{
// 从u的第一条边开始遍历，直到eidx==-1为止
for(int eidx = h[u]; eidx != -1; eidx = nxt[eidx])
{
int v = e[eidx];
int weight = w[eidx];
cout << u << "->" << v << ", weight: " << weight << endl;
}
}
int main()
{
int n, m;
cin >> n >> m;
memset(h, -1, sizeof h); // 初始化h数组为-1
eidx = 0; // 初始化边的编号为0
while(m--)
{
int u, v, weight;
cin >> u >> v >> weight;
add(u, v, weight);
}
for(int u = 1; u <= n; ++u)
iterate(u);
return 0;
}
题目描述
树状数组动态维护区间修改，区间求和的模板题
C++ 代码
#include<bits/stdc++.h>//区间修改 区间求和
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll t1[N],t2[N],n,m,sum[N],x;
inline void add1(ll x,ll k){
for(;x<=n;x+=x&-x)t1[x]+=k;
}
inline void add2(ll x,ll k){
for(;x<=n;x+=x&-x)t2[x]+=k;
}
inline ll ask1(ll x){
ll ans=0;
for(;x;x-=x&-x)ans+=t1[x];
return ans;
}
inline ll ask2(ll x){
ll ans=0;
for(;x;x-=x&-x)ans+=t2[x];
return ans;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>x,sum[i]=sum[i-1]+x;
while(m--){
char s;
cin>>s;
if(s=='C'){
ll l,r,d;
cin>>l>>r>>d;
add1(l,d);
add1(r+1,-d);
add2(l,l*d);
add2(r+1,-(r+1)*d);
}
else {
ll l,r;
cin>>l>>r;
ll ans=(sum[r]+(r+1)*ask1(r)-ask2(r))-(sum[l-1]+l*ask1(l-1)-ask2(l-1));
cout<<ans<<endl;
}
}
}
题目描述
给定一个n个点m条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出impossible。
给定一张边带权的无向图G=(V, E)，其中V表示图中点的集合，E表示图中边的集合，n=|V|，m=|E|。
由V中的全部n个顶点和E中n-1条边构成的无向连通子图被称为G的一棵生成树，其中边的权值之和最小的生成树被称为无向图G的最小生成树。
算法：kruskal算法
时间复杂度：$Mlog(M)$
需要注意
(1)为了枚举边方便，不用使用邻接表或者邻接矩阵进行存储
(2)需要使用并查集维护集合的关系
C++代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=100010,M=2*N;
struct Range
{
int a,b,w;
bool operator<(const Range& r)const{
return w<r.w;
}
}range[M];
int n,m;
int p[N];
int find(int x)
{
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<m;i++){
int a,b,w;
scanf("%d%d%d",&a,&b,&w);
range[i]={a,b,w};
}
sort(range,range+m);
for(int i=1;i<=n;i++)p[i]=i;
int cnt=0;
int res=0;
for(int i=0;i<m;i++){
int a=range[i].a,b=range[i].b;
int fa=find(a),fb=find(b);
if(fa!=fb){
p[fa]=fb;
res+=range[i].w;
cnt++;
}
}
if(cnt!=n-1)cout<<"impossible"<<endl;
else cout<<res<<endl;
return 0;
}
