复习1-图论模板

1.最短路

图全为正权使用Dijkstra,有负权用SPFA,Bellman-Ford稍加了解即可

void spfa(){
    queue<int> q;
    for(int i = 1;i <= n;i++) d[i] = 0x7fffffff;
    q.push(s);vis[s] = 1;d[s] = 0;
    while(!q.empty()){
        int x = q.front();q.pop();vis[x] = 0;
        for(int i = head[x];i;i = G[i].pre){
            int v = G[i].to,w = G[i].v;
            if(d[v] > d[x] + w){
                d[v] = d[x] + w;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
}

SPFA

struct HeapNode{
    int u,d;
    bool operator < (const HeapNode& rhs) const{
        return d > rhs.d;
    }
};

void Dijkstra()
{
    priority_queue<HeapNode> q;
    for(int i = 1;i <= n;i++)
    d[i] = INF;
    d[s] = 0;
    q.push((HeapNode){s,d[s]});
    while(!q.empty()){
        HeapNode x = q.top();q.pop();
        int u = x.u;
        if(x.d > d[u]) continue;
        for(register int i = last[u];i >= 0;i = e[i].next)
        {
            int v = e[i].v,w = e[i].w;
            if(d[u] + w < d[v]){
                d[v] = d[u] + w;
                q.push((HeapNode){v,d[v]});
            }
        }
    }
}

Dijkstra+堆优化

/*
    Bellman-Ford算法 题解上的
*/

#include<iostream>
using namespace std;
const int maxx=10001;
int n,m,s,dis[maxx],w[500001],num[maxx],f[maxx][maxx/10][2],a=0;
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++) dis[i]=400;
    for(int i=1;i<=m;i++)
    for(int j=1;j<=m;j++) w[i]=400;
    for(int i=1;i<=m;i++){
        int x,y,v;
        cin>>x>>y>>v;
        f[x][++num[x]][0]=y;
        f[x][num[x]][1]=i;
        w[i]=v;
    }
    dis[s]=0;
    while(a<=50){ //循环大法好
        for(int i=1;i<=n;i++)
        for(int j=1;j<=num[i];j++)
        dis[f[i][j][0]]=min(dis[f[i][j][0]],dis[i]+w[f[i][j][1]]);
        a++;
    }
    for(int i=1;i<=n;i++) if(dis[i]==400) cout<<2147483647<<‘ ‘; else cout<<dis[i]<<‘ ‘;
    return 0;
}

Bellman-Ford

2.最小生成树

主要掌握Kruskal算法,Prim算法稍加了解即可

/*
     适用于稀疏图
*/
#include <bits/stdc++.h>

using namespace std;

int p[5005];
int n,m,num = 0;

struct node
{
    int x,y,z;
}e[200005];

int cmp(node a,node b)
{
    return a.z < b.z;
}

int find(int x)
{
    return p[x] == x ? x : p[x] = find(p[x]);
}

int Kruskal()
{
    for(int i = 1;i <= n;i++) p[i] = i;
    sort(e+1,e+m+1,cmp);
    int ans = 0,cnt = 0;
    for(int i = 1;i <= m;i++)
    {
        int x = find(e[i].x);
        int y = find(e[i].y);
        if(x != y)
        {
            p[x] = y;
            ans += e[i].z;
            cnt++;
        }
        if(cnt == n-1) break;
    }
    return ans;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1; i <= m;i++)
    {
        scanf("%d%d%d",&e[i].x,&e[i].y,&e[i].z);
    }
    printf("%d\n",Kruskal());
    return 0;
}

Kruskal算法

/*
    适用于稠密图(然而没啥用)
*/

#include <bits/stdc++.h>

using namespace std;

const int maxn = 5010;
const int INF = 0x7fffffff;

int n,m,cnt,head[maxn],dis[maxn],vis[maxn];

struct node{
    int to,v,pre;
}e[400010];

void addedge(int from,int to,int v){
    e[++cnt].pre=head[from];
    e[cnt].to=to;
    e[cnt].v=v;
    head[from]=cnt;
}

int Prim(){
    memset(dis,0x3f,sizeof(dis));
    dis[1]=0;int ans = 0;
    for(int i = 1;i <= n;i++){
        int minn = INF,k = 0;
        for(int j = 1;j <= n;j++){
            if(!vis[j] && dis[j] < minn){
                minn = dis[j];
                k = j;
            }
        }
        if(minn == INF)break;
        vis[k] = 1;
        for(int j = head[k];j;j = e[j].pre){
            int f = e[j].to;
            if(!vis[f])
                dis[f] = min(dis[f],e[j].v);
        }
    }
    for(int i = 1;i <= n;i++) ans += dis[i];
    return ans;
}

int main(){
    scanf("%d%d",&n,&m);
    int x,y,z;
    for(int i = 1;i <= m;i++){
        scanf("%d%d%d",&x,&y,&z);
        addedge(x,y,z);addedge(y,x,z);
    }
    printf("%d\n",Prim());
    return 0;
}

Prim算法

3.LCA

主要理解倍增法,树剖也可以了解,Tarjan就算了

/*
    倍增写法 常数略大
    我觉得不太好理解 所以我不用倍增了
*/
#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500010;

int deep[MAXN],f[MAXN][25],lg[MAXN],head[MAXN],cnt;
int n,m,s;

struct node{
    int to,pre;
}G[MAXN*2];

void add(int from,int to){
    G[++cnt].to = to;
    G[cnt].pre = head[from];
    head[from] = cnt;
}

inline int read() {
     int x = 0,m = 1;
     char ch;
     while(ch < ‘0‘ || ch > ‘9‘)  {if(ch == ‘-‘) m = -1;ch = getchar();}
     while(ch >= ‘0‘ && ch <= ‘9‘){x = x*10+ch-‘0‘;ch=getchar();}
     return m * x;
 }

inline void dfs(int u)
{
    for(int i = head[u];i;i = G[i].pre)
    {
        int v = G[i].to;
        if(v != f[u][0])
        {
            f[v][0] = u;
            deep[v] = deep[u] + 1;
            dfs(v);
        }
    }
}

inline int lca(int u,int v)
{
    if(deep[u] < deep[v]) swap(u,v);
    int dis = deep[u] - deep[v];
    for(register int i = 0;i <= lg[n];i++)
    {
        if((1 << i) & dis) u = f[u][i];
    }
    if(u == v) return u;
    for(register int i = lg[deep[u]];i >= 0;i--)
    {
        if(f[u][i] != f[v][i])
        {
            u = f[u][i];v = f[v][i];
        }
    }
    return f[u][0];
}

inline void init()
{
    for(register int j = 1;j <= lg[n];j++)
    {
        for(register int i = 1;i <= n;i++)
        {
            if(f[i][j-1] != -1)
            f[i][j] = f[f[i][j-1]][j-1];
        }
    }
}

int main()
{
    int x,y,a,b;
    n = read();m = read();s = read();
    for(register int i = 1;i <= n;i++)
    {
        lg[i] = lg[i-1] + (1 << lg[i-1] + 1 == i);
    }
    for(register int i = 1;i <= n-1;i++)
    {
        x = read();y = read();
        add(x,y);add(y,x);
    }
    dfs(s);
    init();
    while(m--)
    {
        a = read();b = read();
        printf("%d\n",lca(a,b));
    }
    return 0;
}

倍增

/*
    这种树剖写法好理解(好背)
    虽然代码比倍增略长 但是也比倍增快
    简直完美2333333
    所以以后就用这种方法辣
*/

#include <bits/stdc++.h>

using namespace std;

const int maxn = 500005;

int fa[maxn],top[maxn],id[maxn],son[maxn],depth[maxn],size[maxn];//树剖要用的所有数组
int n,m,s,head[maxn],cnt;

struct node{
    int to,pre;
}G[maxn*2];

void addedge(int from,int to){
    G[++cnt].to = to;
    G[cnt].pre = head[from];
    head[from] = cnt;
}

void dfs1(int x){
    size[x] = 1;
    for(int i = head[x];i;i = G[i].pre){
        int cur = G[i].to;
        if(cur == fa[x]) continue;
        depth[cur] = depth[x] + 1;
        fa[cur] = x;
        dfs1(cur);
        size[x] += size[cur];
        if(size[cur] > size[son[x]]) son[x] = cur;
    }
}

void dfs2(int x,int t){
    top[x] = t;
    if(son[x]) dfs2(son[x],t);
    for(int i = head[x];i;i = G[i].pre){
        int cur = G[i].to;
        if(cur != fa[x] && cur != son[x])
            dfs2(cur,cur);
    }
}

int lca(int x,int y){
    while(top[x] != top[y]){
        if(depth[top[x]] < depth[top[y]]) swap(x,y);
        x = fa[top[x]];
    }
    if(depth[x] > depth[y]) swap(x,y);
    return x;
}

int main(){
    int x,y,a,b;
    scanf("%d%d%d",&n,&m,&s);
    for(int i = 1;i < n;i++){
        scanf("%d%d",&x,&y);
        addedge(x,y);addedge(y,x);
    }
    dfs1(s);
    dfs2(s,s);
    while(m--){
        scanf("%d%d",&a,&b);
        printf("%d\n",lca(a,b));
    }
    return 0;
}

树剖

/*
    Tarjan算法(题解) 常数挺大的,不推荐,容易被卡
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cctype>
#include <cstring>
#include <queue>
#include <map>
#define ll long long
#define ri register int
#define ull unsigned long long
using namespace std;
const int maxn=500005;
const int inf=0x7fffffff;
template <class T>inline void read(T &x){
    x=0;int ne=0;char c;
    while(!isdigit(c=getchar()))ne=c==‘-‘;
    x=c-48;
    while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48;
    x=ne?-x:x;
    return ;
}
int n,m,s,t;
struct Edge{
    int ne,to;
}edge[maxn<<1];
struct QU{
    int d,id;
    QU(int x,int y){d=x,id=y;}
    QU(){;}
};
vector <QU>q[maxn];
int h[maxn],num_edge=0,ans[maxn];
inline void add_edge(int f,int to){
    edge[++num_edge].ne=h[f];
    edge[num_edge].to=to;
    h[f]=num_edge;
    return;
}
int fa[maxn],vis[maxn];
int get(int x){
    if(fa[x]!=x)fa[x]=get(fa[x]);
    return fa[x];
}
void dfs(int cur){
    int u,v;
    vis[cur]=1;
    for(ri i=h[cur];i;i=edge[i].ne){
        v=edge[i].to;
        if(vis[v])continue;
        dfs(v);
        fa[v]=cur;//dfs后再合并
    }
    for(ri i=0;i<q[cur].size();i++){
        u=q[cur][i].d,v=q[cur][i].id;
        if(vis[u]==2){
            ans[v]=get(u);
        }
    }
    vis[cur]=2;//dfs过
    return ;
}
int main(){
    int x,y;
    read(n),read(m),read(s);
    for(ri i=1;i<n;i++){
        read(x),read(y);
        add_edge(x,y);
        add_edge(y,x);
        fa[i]=i;
    }fa[n]=n;
    for(ri i=1;i<=m;i++){
        read(x),read(y);
        //q[x].push_back(y);q[y].push_back(x);
        q[x].push_back(QU(y,i));
        q[y].push_back(QU(x,i));
    }
    dfs(s);
    for(ri i=1;i<=m;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}

Tarjan

4.二分图最大匹配

要会

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e3+5;

vector<int> G[maxn];
int link[maxn],vis[maxn],n,m,e;

bool dfs(int x){
    for(int i = 0;i < G[x].size();i++){
        int v = G[x][i];
        if(!vis[v]){
            vis[v] = 1;
            if(!link[v] || dfs(link[v])){
                link[v] = x;return true;
            }
        }
    }
    return false;
}

int main()
{
    int x,y;
    scanf("%d%d%d",&n,&m,&e);
    for(int i = 1;i <= e;i++){
        scanf("%d%d",&x,&y);
        if(x <= n && y <= m) G[x].push_back(y);
    }
    int ans = 0;
    for(int i = 1;i <= n;i++){
        memset(vis,0,sizeof(vis));
        if(dfs(i)) ans++;
    }
    printf("%d\n",ans);
    return 0;
}

匈牙利算法

5.Tarjan

全部要会

vector<int> G[maxn];  //vector邻接表存图
int pre[maxn],low[maxn],sccno[maxn],cnt,scccnt;
//pre[i]表示节点i被搜到的次序,lowlink[i]表示i及其后代能追溯到的最早的点v的
//pre[v]值,sccno[i]就是i所在的强连通分量的编号,dfs_clock表示第几次dfs,
//scc_cnt表示找到的强连通分量序号的临时值
stack<int> S;//存储dfs到的每一个点 

void dfs(int u)
{
    pre[u] = low[u] = ++cnt;//先把pre和lowlink初始化为dfs的时间戳
    S.push(u);
    for(int i = 0;i < G[u].size();i++)//遍历与点u相连的所有点
    {
        int v = G[u][i];//取点
        if(!pre[v]){//如果点v没有遍历过
            dfs(v);//深搜
            low[u] = min(low[u],low[v]);//向上合并lowlink的值
        } else if(!sccno[v])//此时v已经搜过,但是不属于任何一个scc,那么就说明已经形成了环
        {
            low[u] = min(low[u],pre[v]);
        }
    }
    if(low[u] == pre[u]){//如果u为最先搜到的点,它就是这个scc的根节点
    scccnt++;
    for(;;)
    {
        int x = S.top();S.pop();//取一个搜过的点
        sccno[x] = scccnt;//它属于这个强联通分量
        if(x == u) break;//直到栈中
         }
    }
 } 

 void find_scc(int n)
 {
    cnt = scccnt = 0;
    memset(sccno,0,sizeof(sccno));
    memset(pre,0,sizeof(pre));
    for(int i = 1;i <= n;i++)
    if(!pre[i]) dfs(i);
 }

求强连通分量

/*
     易得出状态转移为val[v] = max(val[v],val[pre] + a[v])
     于是通过tarjan算法把所有环缩为一点,跑一遍DAG上的DP即可
*/
#include <bits/stdc++.h>

using namespace std;

const int maxn = 10e5+5;

int scc[maxn],dfn[maxn],low[maxn],stac[maxn];
int a[maxn],head1[maxn],head2[maxn],vis[maxn];
int val[maxn],cnt,cnt1,scc_clock,top,n,m,tot,scc_amount;

struct node{
    int to,from,pre;
}g1[maxn*2],g2[maxn*2];//g1为原来的图,g2为缩点后的图 

void add1(int from,int to){
    g1[++cnt].from = from;
    g1[cnt].to = to;
    g1[cnt].pre = head1[from];
    head1[from] = cnt;
} //对应g1的add操作 

void add2(int from,int to){
    g2[++cnt1].from = from;
    g2[cnt1].to = to;
    g2[cnt1].pre = head2[from];
    head2[from] = cnt1;
} //对应g2的add操作 

void tarjan(int x){
    low[x] = dfn[x] = ++scc_clock;//初始化为时间戳
    stac[++top] = x;vis[x] = 1;//入栈、标志数组设为1
    for(register int i = head1[x];i;i = g1[i].pre){//遍历与x连接的点
        int v = g1[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[x] = min(low[x],low[v]);
        }else if(vis[v]){
            low[x] = min(low[x],dfn[v]);
        }
    }//一顿tarjan的操作
    if(low[x] == dfn[x]){
        scc_amount++;
        int y;
        while(y = stac[top--]){//出栈
            scc[y] = x;
            vis[y] = 0;//我也不知道为啥
            if(x == y) break;
            a[x] += a[y];//加权值
        }
    }
}

int dfs(int u){
    val[u] = a[u];
    for(int i = head2[u];i;i = g2[i].pre){
        int v = g2[i].to;
        dfs(v);
        val[v] = max(val[v],val[u] + a[v]);
    }
}

int main(){
    int x,y;
    scanf("%d%d",&n,&m);
    for(register int i = 1;i <= n;i++){
        scanf("%d",a+i);
    }
    for(register int i = 1;i <= m;i++){
        scanf("%d%d",&x,&y);
        add1(x,y);
    }
    for(register int i = 1;i <= n;i++){
        if(!dfn[i]) tarjan(i);//tarjan算法基本操作
    }
    for(register int i = 1;i <= m;i++){
        x = scc[g1[i].from],y = scc[g1[i].to];
        if(x != y){//如果不属于同一强连通分量,就连边
            add2(x,y);
        }
    }
    int ans = 0;
    for(int i = 1;i <= scc_amount;i++){
        if(!val[i]){
            dfs(i);
            ans = max(ans,val[i]);
        }
    }
    printf("%d\n",ans);
    return 0;
}

缩点

/*
无向图割点
对该图进行一次 Tarjan 算法(这里注意在搜索树中把无向边当做有向边看。即LOW[u]=min(LOW[u],DFN[v])(v 是 u 的祖先)的条件变为(v 是 u 的祖先且 v 不是 u 的父亲))这样之后枚举搜索树上的所有边(u,v),若存在 LOW[v]>=DNF[u],则 u 是割点。
无向图割边
对该图进行一次 Tarjan 算法(这里注意在搜索树中把无向边当做有向边看。即LOW[u]=min(LOW[u],DFN[v])(v 是 u 的祖先)的条件变为(v 是 u 的祖先且 v 不是 u 的父亲))这样之后枚举搜索树上的所有边(u,v),若存在 LOW[v]>DNF[u],则(u,v)为割边。
*/
#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;

int low[maxn],dfn[maxn],cut[maxn];
int n,m,cnt;
vector<int> G[maxn];

void tarjan(int x,int father){
    int child = 0;
    low[x] = dfn[x] = ++cnt;
    for(int i = 0;i < G[x].size();i++){
        int v = G[x][i];
        if(!dfn[v]){
            tarjan(v,father);
            low[x] = min(low[x],low[v]);
            if(dfn[x] <= low[v] && x != father) cut[x] = 1;
            if(x == father) child++;
        }
        low[x] = min(low[x],dfn[v]);
    }
    if(x == father && child >= 2) cut[x] = 1;
}

int main(){
    int x,y;
    scanf("%d%d",&n,&m);
    for(int i = 1;i <= m;i++){
        scanf("%d%d",&x,&y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    int ans = 0;
    for(int i = 1;i <= n;i++) if(!dfn[i]) tarjan(i,i);
    for(int i = 1;i <= n;i++){
        if(cut[i]) ans++;
    }
    printf("%d\n",ans);
    for(int i = 1;i <= n;i++){
        if(cut[i]) printf("%d ",i);
    }
    return 0;
}

求割点

6.树上差分

7.拓扑排序

原文地址:https://www.cnblogs.com/bryce02/p/9931332.html

时间: 11-08

复习1-图论模板的相关文章

django复习--如何设置模板路径

设置模板路径:在settings.py中找到templates,添加红色部分,表示设置路径到与setting.py上级目录同级的"templates"文件夹下 TEMPLATES = [ { 'BACKEND': 'django.template.backends.django.DjangoTemplates', 'DIRS': [os.path.join(BASE_DIR, 'templates')] , 'APP_DIRS': True, 'OPTIONS': { 'context

图论模板目录

最短路模板:http://www.cnblogs.com/geloutingyu/p/6511586.html 次短路模板:http://www.cnblogs.com/geloutingyu/p/6528406.html k短路模板: http://www.cnblogs.com/geloutingyu/p/6532945.html 最小生成树模板:http://www.cnblogs.com/geloutingyu/p/5988519.html 最小树形图模板:http://www.cnbl

HDU-4544 湫湫系列故事——消灭兔子

湫湫减肥 越减越肥! 最近,减肥失败的湫湫为发泄心中郁闷,在玩一个消灭免子的游戏. 游戏规则很简单,用箭杀死免子即可. 箭是一种消耗品,已知有M种不同类型的箭可以选择,并且每种箭都会对兔子造成伤害,对应的伤害值分别为Di(1 <= i <= M),每种箭需要一定的QQ币购买. 假设每种箭只能使用一次,每只免子也只能被射一次,请计算要消灭地图上的所有兔子最少需要的QQ币. Input输入数据有多组,每组数据有四行: 第一行有两个整数N,M(1 <= N, M <= 100000),分

NOIP2016纪录[那些我所追求的]

人生第一场正式OI [序] 2016-12-04 见底部 [Day -1] 2016-11-17 期中考试无心插柳柳成荫,考了全市第2班里第1(还不是因为只复习了不到两天考试),马上请了一个周的假准备NOIP(数学生物还是回去上课的) 灰哥跟我一块,tlq考吃了没请假 正好下个周老班出去学习了不害怕 星期4所有人都请假了,漫无目的地复习了一天题,参考题解补了一场模拟赛 晚上灰哥因为住宿直接回家了,还让我给XXX送纸条(不是都有小马了嘛) SD NOIP的群好多人直播,我们就直播了个国际象棋(竟然

模板复习【updating】

马上就要noi了--可能滚粗已经稳了--但是还是要复习模板啊 LCT: bzoj2049 1A 7min # include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long dou

洛谷P3385 【模板】负环 DFS-SPFA 判负环 图论

洛谷P3385 [模板]负环 图论 今天get了 一个 DFS-SPFA 判负环的方法 一般的 BFS-SPFA 判负环 一般就是 不停地做,如果某点第 n+1次加入队列中,那么说明这个图存在负环然而我并不会证明,期望复杂度是 O(kM) k 大约是在 2 左右 但是其实对于一些极限数据,最坏可以把他卡到 O( NM) 额,这就直接炸飞了是不是,而且据说,一些数据比较强的题目,总会想到卡一卡SPFA的, 然后我们换一种思路 因为题目中一定存在一种 负环对吧,所以说假如你某段路径权值和为自然数的时

C++智能指针模板类复习

//C++智能指针模板类复习 #include<iostream> #include<memory> using namespace std; //智能指针用于确保程序不存在内存和资源泄漏且是异常安全的. //C++98中提供了auto_ptr,C++11摒弃了auto_ptr,并提出了unique_ptr .shared_ptr.weak_ptr void show1() { int* p = new int(4); cout << *p << endl;

图论--有向图强连通分量的标记及缩点模板

有向图中在若两点之间可以互相到达,则称这两点强连通,如果一个点集内的所有点都可以互相到达,那么这个点集就是图的一个强连通分量,而我们需要找出有向图中的所有极大强连通分量,于是就用Tarjan算法进行强连通,并将一个连通块缩成一个点,这样就可以形成了一张有向无环图,对解题会很有帮助. 找强连通分量的方法就是 dfs 寻找某个点以及它的后继节点能够到达的最远祖先节点,如果这个最远祖先节点就是进入 dfs 的点,说明所有搜到的后继节点都是在这个强连通分量中,就依次将他们标记为同一个强连通分量. hea

图论常用算法之二 算法模板及建模总结

寒假的第二周,弥补了一下图论算法.在这里做一下总结,主要针对近期学到的一些建模技巧,同时也非常感谢有朋友能够给出图论算法相关的精彩讲解或者知识链接. 算法总结: 欧拉回路问题:判断图是否存在欧拉回路或者欧拉通路,输出一条欧拉回路. 学习Fleury算法输出一条欧拉回路. 1 /* G是连通无向图,则称经过G的每条边一次并且仅一次的路径为 2 欧拉通路,起点和终点是同一个顶点称为欧拉回路,具有欧拉回路的 3 无向图为欧拉图. 4 依次有有向欧拉通路,有向欧拉回路,有向欧拉图 5 定理:连通图G仅有

“玲珑杯”ACM比赛 Round #18 图论你先敲完模板(dp)

题目链接:http://www.ifrog.cc/acm/problem/1146 题意:中文题 题解:状态转移方程:dp[ i ] = min ( dp[ i ] ,dp[ j ] + 2xi-xj+a ). dp[1]=0,第一个点需要消耗的能量为0,从第二个点(假设这个点为A)开始,往前遍历一遍点(假设这个点为B)假定B点为休息点,然后直接到A点需要的能量, 依次然后找出最小能量,因为从第二个点依次往后,每次前面的都已经最优了,所以最后n位置得到的就是答案了. 然后有几个注意点INF尽量弄