11111

//最小生成树
#include
using namespace std;
int cmp(Evode a,Evode b){
    return a.lowcost%cn",Edge[i].Head,Edge[i].Tail);
        }
    }
}

//快速排序 
#include 
int a[101],n;//定义全局变量，这两个变量需要在子函数中使用
void quicksort(int left, int right) {
	int i, j, t, temp;
	if(left > right)
		return;
    temp = a[left]; //temp中存的就是基准数
    i = left;
    j = right;
    while(i != j) { //顺序很重要，要先从右边开始找
    	while(a[j] >= temp && i < j)
    		j--;
    	while(a[i] <= temp && i < j)//再找左边的
    		i++;       
    	if(i < j)//交换两个数在数组中的位置
    	{
    		t = a[i];
    		a[i] = a[j];
    		a[j] = t;
    	}
    }
    //最终将基准数归位
    a[left] = a[i];
    a[i] = temp;
    quicksort(left, i-1);//继续处理左边的，这里是一个递归的过程
    quicksort(i+1, right);//继续处理右边的 ，这里是一个递归的过程
}
int main() {
	int i;
    //读入数据
	scanf("%d", &n);
	for(i = 1; i <= n; i++)
		scanf("%d", &a[i]);
    quicksort(1, n); //快速排序调用
    //输出排序后的结果
    for(i = 1; i < n; i++)
    	printf("%d ", a[i]);
    printf("%dn", a[n]);
    return 0;
}

// 棋盘覆盖问题
#include 
#include
#include
#include
using namespace std;
int title =1;
int a[101][101];
//tr，tc表示棋盘的起始位置(第tr行，第tc列)
//dr，dc表示特殊格子所在位置(第dr行，第dc列)，4*4的棋盘tr，tc取值范围为0,1,2,3
//size表示棋盘大小，4*4的棋盘size为4
void ChessBoard(int tr,int tc,int dr,int dc,int size)
{
    if(size==1)  return;
    int s = size/2;
    int t = title++;
    if(dr=tc+s){//右上
        ChessBoard(tr,tc+s,dr,dc,s);
    }else{
        a[tr+s-1][tc+s] = t;
        ChessBoard(tr,tc+s,tr+s-1,tc+s,s);
    }
    if(dr>=tr+s&&dc=tr+s&&dc>=tc+s){//右下
        ChessBoard(tr+s,tc+s,dr,dc,s);
    }else{
        a[tr+s][tc+s] = t;
        ChessBoard(tr+s,tc+s,tr+s,tc+s,s);
    }
}
int main()
{
    int size;
    scanf("%d",&size);
    for(int i=0;i>x>>y;
    ChessBoard(0,0,x,y,size);
    for(int i=0;i
#include
#include 
#include 

using namespace std;

struct movie {
	int start, end;
};

int cmp(movie a, movie b) {
	return a.end < b.end;
}

int main() {
	int n;
		cin >> n;
		vector arr(n);
		for (int i = 0; i < n; i++) {
			cin >> arr[i].start >> arr[i].end;//输入开始时间和结束时间
		}
		sort(arr.begin(), arr.end(), cmp);//按结束时间从小到大排序
		int end = arr[0].end;//取第一个活动的结束时间
		int sum = 1;//第一个活动一定能放完
		for (int i = 1; i < n; i++) {
			if (arr[i].start < end) {
				continue;//开始时间小于上个活动结束时间的活动不符合要求，跳过
			}
			end = arr[i].end;//更新结束时间
			sum++;
		}
		cout << sum << endl;
	
	return 0;
}

//最小生成树-kruskal
#include
#include
#include
using namespace std;
struct Edge
{
    int x,y,z;
}a[1000010]; //存储x,y,z的信息
bool cmp(const Edge &a,const Edge &b)//比较大小
{
        return a.z
#include
using namespace std;
int main(){
	string a,b;
	cin>>a>>b;
	int len1=a.size();
	int len2=b.size();
	int dp[len1+1][len2+1];
	memset(dp,0,sizeof(dp));
	for(int i=0;i
#include
#include
using namespace std;
#define MaxVertexNum 100
#define INF 9998
typedef struct
{
    char vertex[MaxVertexNum];
    int edges[MaxVertexNum][MaxVertexNum];
    int n,e;
} MGraph;
void CreateMGraph(MGraph &G,int a[][2])
{
    int i,j,k,p;
    cin>>G.n>>G.e;
    for(i=0; i>i>>j>>p;
        G.edges[i][j]=p;
    }
    for(int i=1; i<=2; i++)
        for(int j=1; j<=2; j++)
            cin>>a[i][j];
}

void Ppath(int path[][MaxVertexNum],int i,int j)
{
    int k;
    k=path[i][j];
    if(k==-1)
        return;
    Ppath(path,i,k);
    printf("%d->",k);
    Ppath(path,k,j);
}
void Dispath(int A[][MaxVertexNum],int path[][MaxVertexNum],int n,int a[][2])
{
    int i;
    for(i=1; i<=2; i++)
    {
        int j=1;
        int m=a[i][j];
        int n=a[i][j+1];
        if(A[m][n]==INF)
        {
            if(m!=n)
                printf("%d->%d:-1n",m,n);
        }
        else
        {
            printf("%d->",m);
            Ppath(path,m,n);
            printf("%d:%dn",n,A[m][n]);
        }
    }
}
void bijiao(int A[][MaxVertexNum],MGraph G,int path[][MaxVertexNum])
{
    int max = A[0][0];
    int x=0,y=0;
    for (int i = 0; i < G.n; i++)
        for (int j = 0; j < G.n; j++)
            if (A[i][j]>max&&A[i][j]!=INF)
            {
                max = A[i][j];
                x=i;
                y=j;
            }
    printf("%d->",x);
    Ppath(path,x,y);
    printf("%d:%d",y,A[x][y]);
}

void Floyd(MGraph G,int a[][2])
{
    int i,j,k;
    int A[MaxVertexNum][MaxVertexNum];
    int path[MaxVertexNum][MaxVertexNum];
    for(i=0; iA[i][k]+A[k][j])
                {
                    A[i][j]=A[i][k]+A[k][j];
                    path[i][j]=k;
                }
    Dispath(A,path,G.n,a);
    bijiao(A,G,path);
}
int main()
{
    MGraph G;
    int a[2][2];
    CreateMGraph(G,a);
    Floyd(G,a);
    return 0;
}

//图着色问题 
#include
#include
#include
#include
using namespace std;
int main()
{
    int v,e,k;
    cin>>v>>e>>k;
    int v1,v2;
    vectorvec[v];
    for(int i=0; i>v1>>v2;
        vec[v1-1].push_back(v2-1);
        vec[v2-1].push_back(v1-1);
    }
    int t;
    cin>>t;
    while(t--)
    {
        bool flag=true;
        sets;
        int color[v];
        for(int i=0; i>color[i];
            s.insert(color[i]);
        }
        int len=s.size();
        if(len!=k)
        {
            cout<<"No"<::iterator it;
        for(int i=0; i
using namespace std;

int dp[200][200];//前i个物品装入容量为j的背包中获得的最大价值

//0-1背包动态规划算法   构造二维表
int KnapSack(int n, int w[], int v[], int x[], int C) {
	int i, j;

	for (i = 0; i <= n; i++) { // 初始化：背包容量为0时，前i个物品无法装入，获得最大价值为0
		dp[i][0] = 0;

	}
	for (j = 0; j <= C; j++) {	//初始化：物品数量为0时，背包容量j无论多大，获得最大价值为0
		dp[0][j] = 0;
	}
	for (i = 0;i <= n;i++) {
		if (w[i] > C) {
			dp[i][0] = 0;
		}
	}
	for (i = 1; i <= n; i++) {    //构造二维表：行对应前i个物品；列对应背包容量j
		for (j = 1; j <= C; j++) {
			if (j < w[i]) {		//背包容量不够第i个物品的重量大
				dp[i][j] = dp[i - 1][j]; //不装，获得的最大价值仍然等于前i-1个物品装入情况的
			}
			else {				//装，看看是装入后获得的最大价值大还是前i-1个物品装入情况的最大价值大，比较后选择最大的
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
				
			}
		}
	}
	j = C; //j等于背包的最大容量C
	for (i = n; i > 0; i--) {   //从后往前遍历，如果装了第i个物品则标志位x[i]=1
		if (dp[i][j] > dp[i - 1][j]) { //判断第i个物品有没有装进去
			x[i] = 1;		//第i个物品装了进去
			j = j - w[i];	//装了进去就将该物品的重量减去，j为剩余容量
		}
		else {
			x[i] = 0;   //第i个物品没装进去
		}
	}
	for (i = 1; i <= n; i++) {
		if (x[i]==1) {
			cout << i;
			cout << " ";
		}
		
	}	if (dp[n][C] == 0) {
		cout << "No";
		return dp[n][C] = 0;
	}else
		return dp[n][C];
}
int main() {
	int w[100];	//物品的重量
	int v[100];	//物品的价值
	int x[100];	//物品的选取状态
	int i, n, C;
	cin >> n>>C;//物品总数+背包总容量
	for (i = 1; i <= n; i++) {
		cin >> w[i]>>v[i];
	}
	int maxValue = KnapSack(n, w, v, x, C);
	cout << endl;
	cout <<  maxValue << endl;
	return 0;
}