#include <iostream> #include<vector> #include<algorithm> #include<math.h> using namespace std; //习题11.5 const int maxn=26;//0-25 const int maxint=1000000; int father[maxn]; int height[maxn]; struct edge{ int node1; int node2; int dist; }; edge graph[maxn*maxn]; //初始化 void ini...

最小生成树的变体，没有给边的权重，而是给了节点信息。对于每一个节点对，可以计算出边的权重，然后再用kruskal算法解决。 #include <iostream> #include<vector> #include<algorithm> #include<math.h> using namespace std; //习题11.4 const int maxn=1010; int father[maxn]; int height[maxn]; struct edge{ int node1; int node2; float dist; }; str...

另一种更简便的方法是 可以 直接把权值设成0，这样他们就一定会优先级最高。 #include <iostream> #include<vector> #include<algorithm> using namespace std; //例题11.4 const int maxn=110; int father[maxn]; int height[maxn]; //初始化 void initial(){ for(int i=0;i<maxn;i++){ father[i]=-1; height[i]=0; } } //Find int Find(int ...

kruskal解决最小生成树问题 #include <iostream> #include<vector> #include<algorithm> using namespace std; //例题11.4 const int maxn=110; int father[maxn]; int height[maxn]; //初始化 void initial(){ for(int i=0;i<=maxn;i++){ father[i]=-1; height[i]=0; } } //Find int Find(int x){ if (father[x]==-...

#include <iostream> #include<vector> #include<algorithm> using namespace std; //习题11.1 找出直系亲属 struct TreeNode{ char data; TreeNode *leftchild; TreeNode *rightchild; TreeNode *father; TreeNode(int data):data(data),leftchild(NULL),rightchild(NULL),father(NULL){} }; TreeNode *root=NUL...

真是究极麻烦的一道并查集！！ #include <iostream> #include<vector> #include<algorithm> using namespace std; const int maxn=20000; int father[maxn]; int height[maxn]; int number[maxn];//帮派总人数 int weight[maxn];//帮派总权重 int visit[maxn]; int relation[maxn];//每个人的权重 struct tuanhuo{ string head; int peo...

#include <iostream> using namespace std; //习题11.2 第一题 const int maxn=1000010; int father[maxn]; int height[maxn]; int visit[maxn]; //初始化 void initial(){ for(int i=0;i<=maxn;i++){ father[i]=-1; height[i]=0; visit[i]=0; } } //Find int Find(int x){ if (father[x]==-1)return x; return Find(fathe...

树： 要求1：每个节点入度<=1; 要求2：(连通分量=1&&根=1)||(连通分量=0&&根=0) #include <iostream> using namespace std; const int maxn=100010; int father[maxn]; int height[maxn]; int indegree[maxn]; int visit[maxn]; //初始化 void initial(){ for(int i=0;i<=maxn;i++){ father[i]=-1; height[i]=0; indegree[...

#include <iostream> using namespace std; int father[100010]; int height[100010]; void initial(int n){ for(int i=0;i<=n;i++){ father[i]=-1; height[i]=0; } } int Find(int x){ if (father[x]==-1)return x; return Find(father[x]); } void Union(int x,int y){ int fx=Find(x); int fy=Find(y); if (fx=...

并查集的实现 #include <iostream> using namespace std; int father[100010]; int height[100010]; void initial(int n){ for(int i=0;i<=n;i++){ father[i]=-1; height[i]=0; } } int Find(int x){ if (father[x]==-1)return x; return Find(father[x]); } void Union(int x,int y){ int fx=Find(x); int fy=Find(y); ...

#include <iostream> using namespace std; //最长公共子序列 int dp[100][100]; int longest(string s1,string s2){ int ans=0; int n1=s1.size(); int n2=s2.size(); for(int i=-1;i<n1;i++){ for(int j=-1;j<n2;j++){ if(i==-1||j==-1) dp[i+1][j+1]=0; else if(s1[i]==s2[j]) dp[i+1][j+1]=dp[i][j]+1; else dp[i+...

最长【先递增后递减子序列】 #include <iostream> using namespace std; //合唱队形 int num[110]; int inde[110]; int dp[110]; int maxincrease(int n){ for(int i=0;i<110;i++)inde[i]=0; inde[0]=1; for(int i=1;i<=n;i++){ inde[i]=1; for(int j=0;j<i;j++){ if(num[j]<num[i]) inde[i]=max(inde[i],inde[j]+1); } } ...

max(dp[i],max(dp[j]+num[i]|num[j]<num[i]) #include <iostream> using namespace std; //最大上升子序列和 int num[1010]; int dp[1010]; int maxincrease(int n){ int ans=0; dp[0]=num[0]; for(int i=1;i<n;i++){ dp[i]=num[i]; for(int j=0;j<i;j++){ if(num[j]<num[i]) dp[i]=max(dp[i],dp[j]+num[i]); } a...

除了顺序变成逆序之外，完全标准的最长递增子序列问题模板问题。  #include <iostream> using namespace std; ​ //拦截导弹 int num[30]; int dp[30]; ​ int maxdecrease(int n){ int ans=0; dp[0]=1; for(int i=1;i<n;i++){ int before=-1;//前面>=当前值中，最大的连续序列数 int flag=0;//默认前面没有比它大的 for(int j=0;j<i;j++){ if(num[j]>=num[i]){ flag=1;...