单源最短路问题

德克萨斯纯朴的民众们这个夏天正在遭受巨大的热浪！！！

他们的德克萨斯长角牛吃起来不错，可是它们并不是很擅长生产富含奶油的乳制品。

农夫John此时身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

John已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。

这些路线包括起始点和终点一共有 T 个城镇，为了方便标号为 1 到 T。

除了起点和终点外的每个城镇都由 双向道路 连向至少两个其它的城镇。

每条道路有一个通过费用（包括油费，过路费等等）。

给定一个地图，包含 C 条直接连接 2 个城镇的道路。

每条道路由道路的起点 Rs，终点 Re 和花费 Ci 组成。

求从起始的城镇 Ts 到终点的城镇 Te 最小的总费用。

输入格式
第一行: 4 个由空格隔开的整数: T,C,Ts,Te;

第 2 到第 C+1 行: 第 i+1 行描述第 i 条道路，包含 3 个由空格隔开的整数: Rs,Re,Ci。

输出格式
一个单独的整数表示从 Ts 到 Te 的最小总费用。

数据保证至少存在一条道路。

数据范围
1≤T≤2500,
1≤C≤6200,
1≤Ts,Te,Rs,Re≤T,
1≤Ci≤1000
输入样例：
7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1
输出样例：
7

//SPFA算法
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

const int N = 20000;
int head[N],to[N],nxt[N],w[N],idx=1;
int v[N],n,m,s,t,d[N];
queue<int> q;

void add(int a,int b,int c)
{
    to[idx]=b;
    w[idx]=c;
    nxt[idx]=head[a];
    head[a]=idx++;
}

int spfa()
{
    memset(d,0x3f,sizeof(d));
    d[s]=0;
    v[s]=true;
    q.push(s);
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        v[t]=false;
        for(int i=head[t];i!=-1;i=nxt[i])
        {
            int j=to[i];
            if(d[j]>d[t]+w[i])
            {
                d[j]=d[t]+w[i];
                if(!v[j])
                {
                    q.push(j);
                    v[j]=true;
                }
            }
        }
    }
    
    return d[t];
}

int main()
{
    cin>>n>>m>>s>>t;
    memset(head,-1,sizeof(head));
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    
    cout<<spfa();
}

---

战争时期，前线有 n 个哨所，每个哨所可能会与其他若干个哨所之间有通信联系。

信使负责在哨所之间传递信息，当然，这是要花费一定时间的（以天为单位）。

指挥部设在第一个哨所。

当指挥部下达一个命令后，指挥部就派出若干个信使向与指挥部相连的哨所送信。

当一个哨所接到信后，这个哨所内的信使们也以同样的方式向其他哨所送信。信在一个哨所内停留的时间可以忽略不计。

直至所有 n 个哨所全部接到命令后，送信才算成功。

因为准备充足，每个哨所内都安排了足够的信使（如果一个哨所与其他 k 个哨所有通信联系的话，这个哨所内至少会配备 k 个信使）。

现在总指挥请你编一个程序，计算出完成整个送信过程最短需要多少时间。

输入格式
第 1 行有两个整数 n 和 m，中间用 1 个空格隔开，分别表示有 n 个哨所和 m 条通信线路。

第 2 至 m+1 行：每行三个整数 i、j、k，中间用 1 个空格隔开，表示第 i 个和第 j 个哨所之间存在 双向 通信线路，且这条线路要花费 k 天。

输出格式
一个整数，表示完成整个送信过程的最短时间。

如果不是所有的哨所都能收到信，就输出-1。

数据范围
1≤n≤100,
1≤m≤200,
1≤k≤1000
输入样例：
4 4
1 2 4
2 3 7
2 4 1
3 4 6
输出样例：
11

//Floyd

#include<iostream>
#include <queue>
#include<cstring>
using namespace std;

const int N = 400;
int d[N][N];
int n,m,k;

int main()
{
    cin>>n>>m;
    memset(d,0x3f,sizeof(d));
    d[1][1]=0;		//一定要初始化距离
    while (m -- )
    {
        int a,b,c;
        cin>>a>>b>>c;
        d[b][a]=d[a][b]=min(d[a][b],c);
    }
    
    
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    
    bool flag=false;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(d[1][i]> 0x3f3f3f3f/2)
        {
            flag=true;
            break;
        }
        ans=max(ans,d[1][i]);
    }
    if(flag)
    {
        cout<<-1<<endl;
    }
    else cout<<ans<<endl;
}

//spfa算法

#include<iostream>
#include <queue>
#include<cstring>
using namespace std;

const int N = 300;
int d[N],v[N];
queue<int> q;
int n,m;
int head[N],to[N],nxt[N],w[N],i=0;

void add(int a,int b,int c)
{
    to[i]=b;
    w[i]=c;
    nxt[i]=head[a];
    head[a]=i++;
}

int spfa()
{
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    q.push(1);
    v[1]=true;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        v[t]=false;
        for(int i=head[t];i!=-1;i=nxt[i])
        {
            int j=to[i];
            if(d[j]>d[t]+w[i])
            {
                d[j]=d[t]+w[i];
                if(!v[j])
                {
                    q.push(j);
                    v[j]=true;
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(d[i]>0x3f3f3f3f/2) return -1;
        ans=max(ans,d[i]);
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    while (m -- )
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a, b, c);
        add(b,a,c);
    }
    
    cout<<spfa();
}

---

农夫John发现了做出全威斯康辛州最甜的黄油的方法：糖。

把糖放在一片牧场上，他知道 N 只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。

当然，他将付出额外的费用在奶牛上。

农夫John很狡猾，就像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。

他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。

农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。

给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。

数据保证至少存在一个牧场和所有牛所在的牧场连通。

输入格式
第一行: 三个数：奶牛数 N，牧场数 P，牧场间道路数 C。

第二行到第 N+1 行: 1 到 N 头奶牛所在的牧场号。

第 N+2 行到第 N+C+1 行：每行有三个数：相连的牧场A、B，两牧场间距 D，当然，连接是双向的。

输出格式
共一行，输出奶牛必须行走的最小的距离和。

数据范围
1≤N≤500,
2≤P≤800,
1≤C≤1450,
1≤D≤255
输入样例：
3 4 5
2
3
4
1 2 1
1 3 5
2 3 7
2 4 3
3 4 5
输出样例：
8

//spfa

#include<iostream>
using namespace std;
#include <queue>
#include<cstring>

const int N = 4000;
int d[N],v[N],id[N];
int head[N],to[N],nxt[N],w[N],i=1;
int n,m,k;
queue<int> q;
void add(int a,int b,int c)
{
    to[i]=b;
    w[i]=c;
    nxt[i]=head[a];
    head[a]=i++;
}

int spfa(int a)
{
    memset(d,0x3f3f3f3f,sizeof(d));
    d[a]=0;
    q.push(a);
    v[a]=true;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        v[t]=false;
        for(int i=head[t];i!=-1;i=nxt[i])
        {
            int j=to[i];
            if(d[j]>d[t]+w[i])
            {
                d[j]=d[t]+w[i];
                if(!v[j])
                {
                    q.push(j);
                    v[j]= true;
                }
            }
        }
    }
    
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        if(d[id[i]]>0x3f3f3f3f/2) return 0x3f3f3f3f;
        ans+=d[id[i]];
    }
    return ans;
}

int main()
{
    cin>>n>>k>>m;
    memset(head,-1,sizeof(head));
    for(int i=1;i<=n;i++) cin>>id[i];
    while (m -- )
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,c);
    }
    
    int ans=0x3f3f3f3f;
    for(int i=1;i<=k;i++)
    {
        ans=min(ans,spfa(i));
    }
    
    cout<< ans;
}

---

在 n 个人中，某些人的银行账号之间可以互相转账。

这些人之间转账的手续费各不相同。

给定这些人之间转账时需要从转账金额里扣除百分之几的手续费，请问 A 最少需要多少钱使得转账后 B 收到 100 元。

输入格式
第一行输入两个正整数 n,m，分别表示总人数和可以互相转账的人的对数。

以下 m 行每行输入三个正整数 x,y,z，表示标号为 x 的人和标号为 y 的人之间互相转账需要扣除 z% 的手续费 ( z<100 )。

最后一行输入两个正整数 A,B。

数据保证 A 与 B 之间可以直接或间接地转账。

输出格式
输出 A 使得 B 到账 100 元最少需要的总费用。

精确到小数点后 8 位。

数据范围
1≤n≤2000,
m≤105
输入样例：
3 3
1 2 1
2 3 2
1 3 3
1 3
输出样例：
103.07153164

//Floyd

#include<iostream>
#include <queue>
#include<cstring>
using namespace std;

const int N = 2e5;
int head[N],to[N],nxt[N];
double w[N];
int idx=1;
double d[N];
int v[N],n,m;
queue<int> q;

void add(int a,int b,double c)
{
    to[idx]=b;
    w[idx]=c;
    nxt[idx]=head[a];
    head[a]=idx++;
}

double spfa(int st,int ed)
{
    d[st]=1.0;
    q.push(st);
    v[st]=true;
    while(!q.empty())
    {
        int t=q.front();
        q.pop();
        v[t]=false;
        for(int i=head[t];i!=-1;i=nxt[i])
        {
            int j=to[i];
            if(d[j]<d[t]*w[i])
            {
                d[j]=d[t]*w[i];
                if(!v[j])
                {
                    q.push(j);
                    v[j]=true;
                }
            }
        }
    }
    
    return d[ed];
}

int main()
{
    cin>>n>>m;
    memset(head,-1,sizeof(head));
    while (m -- )
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,1-c*0.01);
        add(b,a,1-c*0.01);
    }
    int s,e;
    cin>>s>>e;
    printf("%.8lf",100/spfa(s,e));
}

Clear And Present Danger S

思路：floyd算法

//Floyd

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 5000;
int n, m, val[N],d[N],v[N];
int head[N], to[N], nxt[N], w[N], index1 = 0;
queue<int> q;
int route[N];
int a[N][N];

void add(int a, int b, int c)
{
	to[index1] = b;
	w[index1] = c;
	nxt[index1] = head[a];
	head[a] = index1++;
}

int main()
{
	cin >> n >> m;
	 
	for (int i = 1; i <= m; i++)
	{
		cin >> route[i];
	}

	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int w;
			cin >> w;
			a[i][j] = w;
		}
	}
	
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
			}
		}
	}
	int ans = 0;
	for (int i = 1; i < m; i++)
	{
		ans += a[route[i]][route[i + 1]];
	}

	cout << ans;
}

欧拉回路问题（一笔画）

#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
int n,m;
int num[1100];

int main()
{
	cin >> n >> m;
	
	while (m--)
	{
		int a, b;
		cin >> a >> b;
		num[a]++;
		num[b]++;
	}
	int ans = 0;
	for (int i = 1; i <=1100; i++)
	{
		if (num[i] & 1) ans++;
	}
	if (ans == 0) cout << 1 << endl;
	else cout << ceil(ans / 2 )<< endl;
	
}

欧拉回路：

若恰通过图中每条边一次回到起点,则称该回路为欧拉(Euler)回路。
具有欧拉回路的图称为欧拉图。
定理1：
一个无向图是欧拉图，当且仅当该图所有顶点度数都是偶数。
一个有向图是欧拉图，当且仅当该图所有顶点度数都是0(入度与出度之和)。
定理2：
存在欧拉回路的条件：图是连通的，且不存在奇点（顶点度数为奇数）

欧拉路（此题解法 ！）

若从起点到终点的路径恰通过图中每条边一次（起点与终点是不同的点），
则该路径称为欧拉路。
定理1：
存在欧拉路的条件：图是连通的，且存在2个奇点。
如果存在2个奇点，则欧拉路一定是从一个奇点出发，以另一个奇点结束。

思路：

统计每个点的度数，如果所有度数都是偶数，则可以一笔画出，否则需要度数为奇数的个数/2次画出

租用游艇

//floyd
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 5000;
int n, m;
int a[N][N];
 

int main()
{
	cin >> n;
 
    memset(a,0x3f,sizeof(a));
	for (int i = 1; i < n; i++)
	{
		for (int j = i + 1;j <= n; j++)
		{
			int x;
			cin >> x;
			if(i==j) a[i][j]=0;
			else a[i][j] = x;
		}
	}

	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
			}
		}
	}

	cout << a[1][n];
}

Cow Party S

思路：spfa，维护两个spfa函数及两个d[N]，spfa1维护d[N]，表示从家到终点的最小距离，spfa2维护d2[N]，表示从终点到各个家中的最短距离。

#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N = 50010, M = 100010;
int n, m, st, ed, val[N], d[N], v[N], d2[N];
int head[N], to[M], nxt[M], w[M], idx = 0;
queue<int> q;

void add(int a, int b, int c)
{
	to[idx] = b;
	w[idx] = c;
	nxt[idx] = head[a];
	head[a] = idx++;
}

void spfa1(int st)
{
	memset(d, 0x3f, sizeof(d));
	d[st] = 0;
	v[st] = true;
	q.push(st);
	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		v[t] = false;
		for (int i = head[t]; i != -1; i = nxt[i])
		{
			int j = to[i];
			if (d[j] > d[t] + w[i])
			{
				d[j] = d[t] + w[i];
				if (!v[j])
				{
					q.push(j);
					v[j] = true;
				}
			}
		}
	}
}

void spfa2(int st)
{
	memset(d2, 0x3f, sizeof(d2));
	d2[st] = 0;
	v[st] = true;
	q.push(st);
	while (!q.empty())
	{
		int t = q.front();
		q.pop();
		v[t] = false;
		for (int i = head[t]; i != -1; i = nxt[i])
		{
			int j = to[i];
			if (d2[j] > d2[t] + w[i])
			{
				d2[j] = d2[t] + w[i];
				if (!v[j])
				{
					q.push(j);
					v[j] = true;
				}
			}
		}
	}
}

int main()
{
	cin >> n >> m >> st;
	memset(head, -1, sizeof(head));
	while (m--)
	{
		int x, y, z;
		cin >> x >> y >> z;
		add(x, y, z);
	}

	spfa1(st);
	int ans = -1;
	for (int i = 1; i <= n; i++)
	{
		spfa2(i);
		if (d[i]+d2[st] > ans) ans = d[i]+d2[st];
	}
	cout << ans;
}

采购特价商品

#include<iostream>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 500, M = 100010;
int n, m, st, ed, val[N], d[N], v[N], d2[N];
int head[N], to[M], nxt[M], w[M], idx = 0;
queue<int> q;
double a[N][N];
 
double getd(double x1, double y1,double x2,double y2)
{
	return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

struct e
{
	int x,y;
}edge[N];

int main()
{
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		int x, y;
		cin >> x >> y;
		edge[i].x = x;
		edge[i].y = y;
	}
	cin >> m;
	memset(a,0x7f,sizeof(a));

	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		a[y][x] = min(a[y][x],getd(edge[x].x, edge[x].y, edge[y].x, edge[y].y));
		a[x][y] = min(a[x][y],getd(edge[x].x, edge[x].y, edge[y].x, edge[y].y));
	}

	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
			}
		}
	}
	cin >> st >> ed;
	printf("%.2lf", a[st][ed]);
}

prim算法

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围
1≤n≤500,
1≤m≤105,
图中涉及边的边权的绝对值均不超过 10000。

输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例：
6

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 550;
int a[N][N],v[N],n,m,d[N];

int prim()
{
    memset(d,0x3f,sizeof(d));
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        int t=-1;
        for(int j=1;j<=n;j++)
        {
            if(!v[j]&&(t==-1||d[t]>d[j]))
            {
                t=j;
            }
        }
        if(i!=1&&d[t]==0x3f3f3f3f) return 0x3f3f3f3f;
        if(i!=1) ans+=d[t];
        
        for(int j=1;j<=n;j++)
        {
            d[j]=min(d[j],a[t][j]);
        }
        
        v[t]=true;
    }

    return ans;
}
int main()
{
    cin>>n>>m;
    memset(a,0x3f,sizeof(a));
    
    while (m -- )
    {
        int x,y,z;
        cin>>x>>y>>z;
        a[x][y]=a[y][x]=min(a[x][y],z);
    }
    
    int ans=prim();
 
    if(ans==0x3f3f3f3f) cout << "impossible"<<endl;
    else cout<<ans<<endl;
}

kruskal算法

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。

求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

给定一张边带权的无向图 G=(V,E)，其中 V 表示图中点的集合，E 表示图中边的集合，n=|V|，m=|E|。

由 V 中的全部 n 个顶点和 E 中 n−1 条边构成的无向连通子图被称为 G 的一棵生成树，其中边的权值之和最小的生成树被称为无向图 G 的最小生成树。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含三个整数 u,v,w，表示点 u 和点 v 之间存在一条权值为 w 的边。

输出格式
共一行，若存在最小生成树，则输出一个整数，表示最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

数据范围
1≤n≤500,
1≤m≤105,
图中涉及边的边权的绝对值均不超过 10000。

输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例：
6

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 203000;
int a[N],n,m;

struct e
{
    int u,v, w;
    bool operator<(const e& aa)
    {
        return w<aa.w;
    }
}edge[N];

int find(int x)
{
    if(x!=a[x]) a[x]=find(a[x]);
    return a[x];
}
int main()
{
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        edge[i].u=x;
        edge[i].v=y;
        edge[i].w=z;
    }
    sort(edge,edge+m);
    for(int i=1;i<=n;i++)
    {
        a[i]=i;
    }
    int ans=0,cnt=0;
    for(int i=0;i<m;i++)
    {
        int u=edge[i].u,v=edge[i].v,w=edge[i].w;
        int x=find(u),y=find(v);
        if(x!=y)
        {
            a[x]=y;
            ans+=w;
            cnt++;
        }
    }
    if(cnt<n-1) cout<<"impossible"<<endl;
    else cout<<ans<<endl;
}

dp最长上升子序列问题

###登山

五一到了，ACM队组织大家去登山观光，队员们发现山上一共有N个景点，并且决定按照顺序来浏览这些景点，即每次所浏览景点的编号都要大于前一个浏览景点的编号。

同时队员们还有另一个登山习惯，就是不连续浏览海拔相同的两个景点，并且一旦开始下山，就不再向上走了。

队员们希望在满足上面条件的同时，尽可能多的浏览景点，你能帮他们找出最多可能浏览的景点数么？

输入格式
第一行包含整数N，表示景点数量。

第二行包含N个整数，表示每个景点的海拔。

输出格式
输出一个整数，表示最多能浏览的景点数。

数据范围
2≤N≤1000
输入样例：
8
186 186 150 200 160 130 197 220
输出样例：
4

#include<bits/stdc++.h> 
using namespace std;

const int N = 1010;
int n,dp[N],a[N],ans=0,len=0;
int f[N],g[N];

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
        cin>>a[i];
    
    for(int i=0;i<n;i++)
    {
        f[i]=1;
        for(int j=0;j<i;j++)
        {
            if(a[j]<a[i])
            {
                f[i]=max(f[i],f[j]+1);
            }
        }
    }
    
    for(int i=n-1;i>=0;i--)
    {
        g[i]=1;
        for(int j=n-1;j>i;j--)
        {
            if(a[j]<a[i])
            {
                g[i]=max(g[i],g[j]+1);
            }
        }
    }

    for(int i=0;i<n;i++)
    {
        ans=max(ans,f[i]+g[i]-1);
    }

    cout<<ans<<endl;
 
}

###最大上升子序列和

一个数的序列 bi，当 b1<b2<…<bS 的时候，我们称这个序列是上升的。

对于给定的一个序列(a1,a2,…,aN)，我们可以得到一些上升的子序列(ai1,ai2,…,aiK)，这里1≤i1<i2<…<iK≤N。

比如，对于序列(1,7,3,5,9,4,8)，有它的一些上升子序列，如(1,7),(3,4,8)等等。

这些子序列中和最大为18，为子序列(1,3,5,9)的和。

你的任务，就是对于给定的序列，求出最大上升子序列和。

注意，最长的上升子序列的和不一定是最大的，比如序列(100,1,2,3)的最大上升子序列和为100，而最长上升子序列为(1,2,3)。

输入格式
输入的第一行是序列的长度N。

第二行给出序列中的N个整数，这些整数的取值范围都在0到10000(可能重复)。

输出格式
输出一个整数，表示最大上升子序列和。

数据范围
1≤N≤1000
输入样例：
7
1 7 3 5 9 4 8
输出样例：
18

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

int a[1010],n,dp[1010];
int ans=0;

int main()
{
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    
    for(int i=0;i<n;i++)
    {
        dp[i]=a[i];
        for(int j=0;j<i;j++)
        {
            if(a[j]<a[i])
            {
                dp[i]=max(dp[i],dp[j]+a[i]);
            }
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans; 
}

拦截导弹

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式
共一行，输入导弹依次飞来的高度。

输出格式
第一行包含一个整数，表示最多能拦截的导弹数。

第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。

数据范围
雷达给出的高度数据是不大于 30000 的正整数，导弹数不超过 1000。

输入样例：
389 207 155 300 299 170 158 65
输出样例：
6
2

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010;
int n,dp[N],a[N],ans,g[N];

int main()
{
    while(cin>>a[n]) n++;
    
    for(int i=0;i<n;i++)
    {
        dp[i]=1;
        for(int j=0;j<i;j++)
        {
            if(a[j]>=a[i])
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
        ans=max(ans,dp[i]);
    }
    cout<<ans<<endl;
    
    ans=0;
    for(int i=0;i<n;i++)
    {
        int k=0;
        while(k<ans &&g[k]<a[i]) k++;
        g[k]=a[i];
        if(k>=ans) ans++;
    }
    cout<<ans;
}

繁忙的都市

最小生成树问题

//kruskal算法
#include<bits/stdc++.h> 
using namespace std;

const int N = 11010;
int n,a[N],m,ans=0;
int f[N];

struct e
{
    int u,v,w;
    bool operator < (const e &rhs) const
    {
        return w < rhs.w;
    }
}edge[N];

int find(int x)
{
    if(f[x]!=x) f[x]=find(f[x]);
    return f[x];
}

void join(int x,int y)
{
    x=find(x);
    y=find(y);
    if(x!=y) f[x]=y;
}

int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        edge[i].u=x;
        edge[i].v=y;
        edge[i].w=z;
    }

    //kruskal
    sort(edge+1,edge+m+1);
    for(int i=1;i<=n;i++)
    {
        f[i]=i;
    }

    int cnt=0;
    for(int i=1;i<=m;i++)
    {
        int x=find(edge[i].u);
        int y=find(edge[i].v);
        if(x!=y)
        {
            join(x,y);
            cnt++;
            ans=edge[i].w;
            if(cnt==n-1) break;
        }
    }

    cout<<n-1<<" "<<ans<<endl;
}

二维费用背包问题

有 N 件物品和一个容量是 V 的背包，背包能承受的最大重量是 M。

每件物品只能用一次。体积是 vi，重量是 mi，价值是 wi。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，总重量不超过背包可承受的最大重量，且价值总和最大。
输出最大价值。

输入格式
第一行三个整数，N,V,M，用空格隔开，分别表示物品件数、背包容积和背包可承受的最大重量。

接下来有 N 行，每行三个整数 vi,mi,wi，用空格隔开，分别表示第 i 件物品的体积、重量和价值。

输出格式
输出一个整数，表示最大价值。

数据范围
0<N≤1000
0<V,M≤100
0<vi,mi≤100
0<wi≤1000
输入样例
4 5 6
1 2 3
2 4 4
3 4 5
4 5 6
输出样例：
8

#include<iostream>
using namespace std;

const int N = 1010;
int dp[N][N],w[N],v[N],wei[N],n,m,l;

int main()
{
    cin>>n>>m>>l;
    for(int i=1;i<=n;i++)
    {
        cin>>v[i]>>wei[i]>>w[i];
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=v[i];j--)
        {
            for(int k=l;k>=wei[i];k--)
            {
                dp[j][k]=max(dp[j][k],dp[j-v[i]][k-wei[i]]+w[i]);
            }
        }
    }
    cout<<dp[m][l];
}

潜水员（多重背包，费用至少为w)

潜水员为了潜水要使用特殊的装备。

他有一个带2种气体的气缸：一个为氧气，一个为氮气。

让潜水员下潜的深度需要各种数量的氧和氮。

潜水员有一定数量的气缸。

每个气缸都有重量和气体容量。

潜水员为了完成他的工作需要特定数量的氧和氮。

他完成工作所需气缸的总重的最低限度的是多少？

例如：潜水员有5个气缸。每行三个数字为：氧，氮的（升）量和气缸的重量：

3 36 120

10 25 129

5 50 250

1 45 130

4 20 119
如果潜水员需要5升的氧和60升的氮则总重最小为249（1，2或者4，5号气缸）。

你的任务就是计算潜水员为了完成他的工作需要的气缸的重量的最低值。

输入格式
第一行有2个整数 m，n。它们表示氧，氮各自需要的量。

第二行为整数 k 表示气缸的个数。

此后的 k 行，每行包括ai，bi，ci，3个整数。这些各自是：第 i 个气缸里的氧和氮的容量及气缸重量。

输出格式
仅一行包含一个整数，为潜水员完成工作所需的气缸的重量总和的最低值。

数据范围
1≤m≤21,
1≤n≤79,
1≤k≤1000,
1≤ai≤21,
1≤bi≤79,
1≤ci≤800
输入样例：
5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119
输出样例：
249

//完全背包 求费用至少为w

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 1010;
int n,m,k,o2[N],n2[N],w[N];
int dp[N][N];

int main()
{
    cin>>m>>n>>k;
    memset(dp,0x3f,sizeof(dp));
    dp[0][0]=0;
    for(int i=1;i<=k;i++)
    {
        cin>>o2[i]>>n2[i]>>w[i];
    }
    
    for(int i=1;i<=k;i++)
    {
        for(int j=m;j>=0;j--)
        {
            for(int k=n;k>=0;k--)
            {
                dp[j][k]=min(dp[j][k],dp[max(0,j-o2[i])][max(0,k-n2[i])]+w[i]);
            }
        }
    }
    cout<<dp[m][n];
  
}

数字组合（01背包，费用恰好为w）

给定 N 个正整数 A1,A2,…,AN，从中选出若干个数，使它们的和为 M，求有多少种选择方案。

输入格式
第一行包含两个整数 N 和 M。

第二行包含 N 个整数，表示 A1,A2,…,AN。

输出格式
包含一个整数，表示可选方案数。

数据范围
1≤N≤100,
1≤M≤10000,
1≤Ai≤1000,
答案保证在 int 范围内。

输入样例：
4 4
1 1 2 2
输出样例：
3

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100111;
int dp[N],n,m,a[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    
    dp[0]=1;
    
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=a[i];j--)
        {
            dp[j]=dp[j]+dp[j-a[i]];
        }
    }
    cout<<dp[m];
}

买书（完全背包，费用恰好为w)

小明手里有n元钱全部用来买书，书的价格为10元，20元，50元，100元。

问小明有多少种买书方案？（每种书可购买多本）

输入格式
一个整数 n，代表总共钱数。

输出格式
一个整数，代表选择方案种数。

数据范围
0≤n≤1000
输入样例1：
20
输出样例1：
2
输入样例2：
15
输出样例2：
0
输入样例3：
0
输出样例3：
1

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;
int a[]={10,20,50,100};
int dp[N],n;

int main()
{
    cin>>n;
    dp[0]=1;
    
    for(int i=0;i<=3;i++)
    {
        for(int j=a[i];j<=n;j++)
        {
            dp[j]+=dp[j-a[i]];
        }
    }
    cout<<dp[n];
}

营救

题目背景
“咚咚咚……”“查水表！”原来是查水表来了，现在哪里找这么热心上门的查表员啊！小明感动得热泪盈眶，开起了门……

题目描述
妈妈下班回家，街坊邻居说小明被一群陌生人强行押上了警车！妈妈丰富的经验告诉她小明被带到了 tt 区，而自己在 ss 区。

该市有 mm 条大道连接 nn 个区，一条大道将两个区相连接，每个大道有一个拥挤度。小明的妈妈虽然很着急，但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 ss 至 tt 的路线，使得经过道路的拥挤度最大值最小。

输入格式
第一行有四个用空格隔开的 nn，mm，ss，tt，其含义见【题目描述】。

接下来 mm 行，每行三个整数 u, v, wu,v,w，表示有一条大道连接区 uu 和区 vv，且拥挤度为 ww。

两个区之间可能存在多条大道。

输出格式
输出一行一个整数，代表最大的拥挤度。

思路：最小生成树

#include<bits/stdc++.h>

using namespace std;
const int N=300000;

int n,m,s,t;
int p[N];
struct e
{
    int u,v,w;
    bool operator <(const e &a) const
    {
        return w<a.w;
    }
}edge[N];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

void join(int x,int y)
{
    int xx=find(x);
    int yy=find(y);
    if(xx!=yy) p[xx]=yy;
}

int main()
{
    cin>>n>>m>>s>>t;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        edge[i]={x,y,z};
    }

    sort(edge+1,edge+1+m);
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int u=edge[i].u,v=edge[i].v,w=edge[i].w;
        if(find(u)!=find(v))
        {
            join(u,v);
        }
        if(find(s)==find(t))	//特判起点到终点
        {
            cout<<w;
            break;
        }
    }
}

分组背包

有 N 组物品和一个容量是 V 的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。

输出最大价值。

输入格式
第一行有两个整数 N，V，用空格隔开，分别表示物品组数和背包容量。

接下来有 N 组数据：

每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；
输出格式
输出一个整数，表示最大价值。

数据范围
0<N,V≤100
0<Si≤100
0<vij,wij≤100
输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例：
8

#include<iostream>
using namespace std;

const int N =  120;
int n,m,dp[N],v[N][N],w[N][N],s[N];

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>s[i];
        for(int j=1;j<=s[i];j++)
        {
            cin>>v[i][j]>>w[i][j];
        }
    }
    
    for(int i=1;i<=n;i++)
    {
        for(int j=m;j>=0;j--)
        {
            for(int k=0;k<=s[i];k++)
            {
                if(j>=v[i][k]) dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
            }
        }
    }
    cout<<dp[m];
}

Q.E.D.