2018 Spring Training 图论 合集

https://cn.vjudge.net/contest/229893#overview 题目链接
A.Uva 302
判断能不能走就是一个一笔画问题，（欧拉回路），因为题目要求是要回到原点，因此所有点的度都必须是偶数才能满足要求。操蛋的是输出路径的时候是要输出路径 编号并且要求输出路径编号字典序最小的路径。本蒟蒻没想到什么好办法，于是每个点拿了一个map存路径，第一个键值是路径的编号，第二个则是路径的另一个端点。
代码写的非常丑陋QAQ
PS:这题在uva和poj上的格式要求不一样，疯狂pe –

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
int e[50][50];vector<int>road;int n;map<int,int>mp[50];bool used[2000];
void euler(int u)
{
    map<int,int>::iterator iter;
    for(iter=mp[u].begin();iter!=mp[u].end();iter++){
        if(!used[iter->first]&&e[u][iter->second]){
            e[u][iter->second]--;e[iter->second][u]--;used[iter->first]=true;
            euler(iter->second);road.push_back(iter->first);//mp[u].erase(iter);
        }
    }
}
int main()
{
    int x,y,z;
    step:while(cin>>x>>y&&x&&y){
        cin>>z;int degree[50]={0};road.clear();memset(used,0,sizeof(used));
        for(int i=1;i<=n;i++)mp[i].clear();
        memset(e,0,sizeof(e));e[x][y]++;e[y][x]++;
        mp[x][z]=y;mp[y][z]=x;
        degree[x]++;degree[y]++;int begin=min(x,y);n=0;
        while(cin>>x>>y&&x&&y){
            cin>>z;
            e[x][y]++;e[y][x]++;
            mp[x][z]=y;mp[y][z]=x;
            degree[x]++;degree[y]++;n=max(n,max(x,y));
        }
        for(int i=1;i<=n;i++)
            if(degree[i]%2){
            puts("Round trip does not exist.");goto step;
        }
        euler(begin);//road.push_back(begin);
        while(road.size()>1){
            cout<<road.back()<<' ';road.pop_back();
        }
        cout<<road.back()<<endl;
        //cout<<endl;
    }

    return 0;
}

B. POJ 1062
题意不太好懂，反正看懂之后就是一个最短路问题，但是有个问题就是等级限制，那么我们就枚举等级限制就好了，从区间[酋长等级-limit,酋长等级]一直枚举到[酋长等级，酋长等级+k]，（题目似乎没有保证酋长等级一定最高？），每次枚举时】那些主人等级不在区间内的物品就被标记为inque，然后跑一发spfa，最后比较所有的最小值即可。（不过当时好像写了dijkstra23333）

#include<cstdio>
#include<vector>
#include<queue>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstring>
using namespace std;
typedef struct {
    int to, cost;
}Edge;
vector<Edge>G[105];
typedef pair<int, int>P;
priority_queue<P, vector<P>, greater<P> >q;
int book[105], dis[105];
int dijkstra(void)
{
    int i,j;
    while (!q.empty()) {
        P p = q.top(); q.pop();
        if (book[p.second] == 1) continue;
        book[p.second] = 1;
        for (i = 0; i < G[p.second].size(); i++) {
            Edge temp = G[p.second][i];if(book[temp.to])continue;
            if (dis[temp.to] > dis[p.second] + temp.cost) {
                dis[temp.to] = dis[p.second] + temp.cost;
                P p1; p1.first = dis[temp.to]; p1.second = temp.to;
                q.push(p1);
            }
        }
    }
    return dis[1];
}
int main(void)
{
    int m,n,i,j,p,l,x,val[105],level1[105];
    cin>>m>>n;
    for(i=1;i<=n;i++){
        scanf("%d%d%d",&val[i],&level1[i],&x);
        for(j=1;j<=x;j++){
            scanf("%d%d",&p,&l);G[p].push_back(Edge{i,l});
        }
    }
    int up,down;int ans=(1<<31)-1;
    for(i=level1[1]-m;i<=level1[1];i++){
        up=i+m;down=i;memset(book,0,sizeof(book));memset(dis,0x3f,sizeof(dis));
        for(j=1;j<=n;j++){
            if(level1[j]<down||level1[j]>up){
                book[j]=1;
            }
            else{
                q.push(P(val[j],j));dis[j]=val[j];
            }
        }
        ans=min(ans,dijkstra());
    }
    cout<<ans<<endl;

    return 0;
}

C. HDU3499
题意:
有一个有向图,你要从特定的城市A飞到城市B去.给你这个图的所有边(航班)信息.但是你手上有一张卡,可以使得某一趟航班的价格减半.现在的问题是你从A到B的最小费用是多少?
首先要知道这条如果让一条原本是最短路径(假设总距离为x)上最长的边变成半价，最终求得的解不一定是最优的。因为假如现在有另外一条路径，假设该路径距离为x+1。且这条路径上只有5条边，4条长为1的边，但是1条长为x-3的边。如果我们让这条路径的x-3边变成半价是不是能得到更好的结果？
明显必须从m条边中枚举那条半价的航班.假设这条半价的航班是i->j的.那么我们必须知道从A到i的最短距离和从j到B的最短距离. 从A到i的最短距离可以通过求A的单源最短路径即可.从j(j有可能是任意点)到B的最短距离必须建立原图的反向图,然后求B到其他所有点的单源最短路径.(想想是不是)
原题输入数据很多,距离要用long long保存.
题目跟cf上某一次的题目还是比较像的。

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
#include<string>
#include<map>
using namespace std;
typedef long long ll;
struct edge{
    int to;ll cost;
};
bool inque[100005];
const int N=1e5+5;
int main()
{
    int n,m,s,e,i,j,k;
    while(cin>>n>>m) {
        ll dis1[100005];memset(dis1,0x3f,sizeof(dis1));map<string,int>mp;//将名字映射为数字编号
        vector<edge>G[100005];vector<edge>G1[N];
        ll dis2[100005];memset(dis2,0x3f,sizeof(dis2));
        //for (i = 1; i <= n; i++)dis[i] = (1 << 31) - 1;
        //dis[s] = 0;
        string str1,str2;int cnt=0;
        for (i = 1; i <= m; i++) {
            cin>>str1>>str2>>j;int a,b;
            if(a=mp[str1]);
            else a=mp[str1]=++cnt;
            if(b=mp[str2]);
            else b=mp[str2]=++cnt;
            G[a].push_back(edge{b,j});G1[b].push_back(edge{a,j});
        }
        cin>>str1>>str2;
        queue<int> que;
        if(s=mp[str1]);
        else s=mp[str1]=++cnt;
        if(e=mp[str2]);
        else e=mp[str2]=++cnt;
        que.push(s);dis1[s]=0;//prevv[s]=0;
        //inque[s] = true;
        while (!que.empty()) {
            int t = que.front();
            que.pop();
            inque[t] = false;
            for (i = 0; i < G[t].size(); i++) {
                edge e = G[t][i];
                if (dis1[e.to] > dis1[t] + e.cost) {
                    dis1[e.to] = dis1[t] + e.cost;//prevv[e.to]=t;prel[e.to]=e.cost;
                    if (!inque[e.to]) {
                        que.push(e.to);
                        inque[e.to] = true;
                    }
                }
            }
        }
        que.push(e);dis2[e]=0;//prevv[s]=0;
        //inque[s] = true;
        while (!que.empty()) {
            int t = que.front();
            que.pop();
            inque[t] = false;
            for (i = 0; i < G1[t].size(); i++) {
                edge e = G1[t][i];
                if (dis2[e.to] > dis2[t] + e.cost) {
                    dis2[e.to] = dis2[t] + e.cost;//prevv[e.to]=t;prel[e.to]=e.cost;
                    if (!inque[e.to]) {
                        que.push(e.to);
                        inque[e.to] = true;
                    }
                }
            }
        }
        ll ans=(1LL<<63)-1;
        for(i=1;i<=n;i++){
            for(j=0;j<G[i].size();j++){//暴力枚举所有边
                edge e=G[i][j];
                ans=min(ans,dis1[i]+dis2[e.to]+e.cost/2);
            }
        }
        if(ans>=0x3f3f3f3f3f3f3f3f){
            cout<<-1<<endl;
        }
        else{
            cout<<ans<<endl;
        }
    }

    return 0;
}

D.HDU5521
题意：给定点数n和集合个数m，然后给你m个集合，每一个集合有si个点，集合内的点两两之间的到达时间都是ti，一个人在1，一个人在n，求两人同时出发的相遇的最短时间（或输出不可能）；

由于每一个集合的点有很多，若集合两两之间连边，边数非常大，一开始这样就超时了……然后正确做法是对每一个集合再虚拟一个节点（范围是[n+1,n+m]），给每一个集合内的点连边权为ti的双向边到本集合对应虚拟节点，集合内其他点不连边，这样就可以通过虚拟的节点来到达其他地方从而减少边数（方法真是太巧妙了），然后求相遇的最短时间，显然现在无法得知到底选哪个地点作为见面地点，那就对1跑一遍单源最短路，对n跑一边单源最短路，然后统计1~n中每一个点的可能最短时间（一个人早到一个人晚到，显然用max取时间长的那个数而不是时间相加！！），然后选出1~n中的最短时间mndx，再遍历一下看哪些点的最短时间为mndx并记录输出，最后记得把最短时间除以2，因为连的边是ti，进入虚拟节点又出来会多算一次

点数为1e5，题目中说了所有集合大小之和不会超过1e6，每一个集合都有2*|Si|条边，那就是2*1e6条边因此N可设为1e5+10，M可设为2*1e6+10。

然而这还不是最优的做法，因为距离/2以后就会涉及到浮点数的问题，可能带来误差
这题是群内的点之间两两距离为ti，那不妨把Block点拆成入口和出口，然后这样连边：

<u, Block入口, 0>,<Block出口, u , 0>,<Block入口, Block出口, ti>

然后从S和T各跑一遍SPFA然后记录下Max更新答案即可，也不用像上面的解法一样除以2了，点数最差情况下一个点作为Block，应该是3e5，边数应该为2sum{Si}+m，应该是2e6+1e5

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
const int N=2e5+5;
struct edge{
    int to;int cost;
};
bool inque[N*2]={0};
int main()
{
    int t;cin>>t;int c=0;
    while(t--) {
        vector<edge>G[N*2];c++;cout<<"Case #"<<c<<": ";
        int n, m, i, j, k;
        cin >> n >> m ;
        int dis[N * 2],dis1[N*2];memset(dis,0x3f,sizeof(dis));memset(dis1,0x3f,sizeof(dis1));

        //for (i = 1; i <= n; i++)dis[i] = (1 << 31) - 1;
        //dis[s] = 0;
        int cnt=1;
        for (i = 1; i <= m; i++) {
            int t,s;scanf("%d%d",&t,&s);//vector<int>temp;
            for(j=1;j<=s;j++){
                scanf("%d",&k);G[k].push_back(edge{n+cnt,0});G[n+cnt+1].push_back(edge{k,0});G[n+cnt].push_back(edge{n+cnt+1,t});
            }
            cnt+=2;
        }
        queue<int> que;que.push(1);dis[1]=0;//记得初始化起点距离QAQ
        while (!que.empty()) {
            int t = que.front();
            que.pop();
            inque[t] = false;
            for (i = 0; i < G[t].size(); i++) {
                edge e = G[t][i];
                if (dis[e.to] > dis[t] + e.cost) {
                    dis[e.to] = dis[t] + e.cost;
                    if (!inque[e.to]) {
                        que.push(e.to);
                        inque[e.to] = true;
                    }
                }
            }
        }
        que.push(n);dis1[n]=0;
        while (!que.empty()) {
            int t = que.front();
            que.pop();
            inque[t] = false;
            for (i = 0; i < G[t].size(); i++) {
                edge e = G[t][i];
                if (dis1[e.to] > dis1[t] + e.cost) {
                    dis1[e.to] = dis1[t] + e.cost;
                    if (!inque[e.to]) {
                        que.push(e.to);
                        inque[e.to] = true;
                    }
                }
            }
        }
        int minn=0x3f3f3f3f;vector<int>ans;
        for(i=1;i<=n;i++){
            if(max(dis[i],dis1[i])<minn){
                minn=max(dis[i],dis1[i]);ans.clear();ans.push_back(i);
            }
            else if(max(dis[i],dis1[i])==minn)
                ans.push_back(i);
        }
        if(minn==0x3f3f3f3f){
            cout<<"Evil John"<<endl;
        }
        else{
            cout<<minn<<endl;
            for(i=0;i<ans.size();i++)
                printf("%d%c",ans[i],i==ans.size()-1?'\n':' ');
        }
    }

    return 0;
}

E.POJ1273
最大流的模板题，没啥好说的，dinic别给敲错了就行，以及n是边数，m是点数这种反人类设计

#include<cstdio>
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
typedef long long ll;
struct edge{
    int to,cap,rev;
};
vector<edge>G[210];
int level[205],iter[205];
void addedge(int from,int to,int cap)
{
    G[from].push_back(edge{to,cap,(int)G[to].size()});
    G[to].push_back(edge{from,0,(int)G[from].size()-1});//反向容量为0!!
}
void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int>que;
    level[s]=0;que.push(s);
    while(!que.empty()){
        int t=que.front();que.pop();
        for(int i=0;i<G[t].size();i++){
            edge e=G[t][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[t]+1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f)
{
    if(v==t)return f;
    for(int&i=iter[v];i<G[v].size();i++){//注意传引用!
        edge&e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;//不要漏了这个,很多时候可能是无法增广的
}
int maxflow(int s,int t){
    int flow=0;
    for(;;){
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while(f=dfs(s,t,0x7f7f7f7f))
            flow+=f;
    }
}
int main()
{
    int n,m,i,j,k;
    while(cin>>n>>m) {
        for(i=1;i<=205;i++)G[i].clear();
        for (i = 1; i <= n; i++) {
            int s, e, c;
            scanf("%d%d%d", &s, &e, &c);
            addedge(s, e, c);
        }
        cout << maxflow(1, m) << endl;
    }

    return 0;
}

F.HDU1272
很明显的并查集。//代码已经没问题了
有几点要注意的：
1.由于这里某个数字不一定会出现，所以要设一个mark来标记数字是否出现过。每次输入一对数字的关系则进行查找根结点的函数,并通过合并函数来判断两个数是否已经联通
2.如果两个数字能查找到相同的根结点就证明二者已经是相通的，再输入二者的关系就变成有多条相通的路径了。这时候答案肯定要输出“No”，如果两个数字不能查找到共同的根结点把两数字所在的集合合并，直到一组数据输入结束后，再进行判断，是否输入的关系每个数字之间都有相通的路径
3.如果每测试数据已0 0输入，也应打印出Yes！ 坑爹设计无力吐槽
之前非常傻缺的把初始化的地方放错位置了结果一直在wa QAQ…

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=1e5+5;
int par[N];
int find(int x)
{
    return par[x]==x?x:par[x]=find(par[x]);//后面这一块不要漏了par[x]!!!否则就是不带路径压缩
}
bool unite(int x,int y)
{
    x=find(x),y=find(y);
    if(x==y)return false;
    par[x]=y;
    return true;
}
int main()
{
    int a,b;
    while(cin>>a>>b&&a!=-1&&b!=-1){
        if(!a&&!b){
            puts("Yes");
            continue;
        }
        for(int i=1;i<=1e5;i++)par[i]=i;
        bool isok=true;unite(a,b);bool exi[N]={0};exi[a]=exi[b]=true;
        int minn=min(a,b),maxn=max(a,b);
        while(scanf("%d%d",&a,&b)&&a&&b){
            exi[a]=exi[b]=true;minn=min(minn,min(a,b));
            maxn=max(maxn,max(a,b));
            if(!unite(a,b))
                isok=false;
        }
        //for(int i=1;i<=8;i++)cout<<par[i]<<endl;
        if(!isok){
            puts("No");continue;
        }
        int root=0;
        for(int i=minn;i<=maxn;i++){
            if(exi[i]&&find(i)==i){
                root++;
            }
        }
        if(root>1)puts("No");
        else puts("Yes");
    }

    return 0;
}```

G.POJ1422
好吧，这其实是一个最小路径覆盖的结论题…如果你不知道结论的话…GG
题意：在一个有向无环图中，从一些顶点出发，能遍历到图上所有点，要求初始选择的顶点数最少且顶点不重复遍历。
思路：
如果从某个顶点开始遍历的过程看成是路径的选择，那么问题就转化为在有向无环图中找最少的不想交的简单路径，这些路径覆盖图中的所有顶点。可见是关于最小路径覆盖的问题。
在有向无环图中，最小路径覆盖数 = 节点数 — 其对应二分图的最大匹配数。
最小路径覆盖它要求原图必须是有向无环图。然后根据原图构造二分图，方法为：将原图中的每个顶点vi一分为二，vi* 和vi**,相应的，如果原图中存在一条从vi到vj的有向边，那么就在顶点 vi* 和 vj** 之间连一条无向边，这就构造出一个路径覆盖问题所对应的二分图，在该二分图的基础上求其最大匹配数。
剩下的就是一个dinic的问题了

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
using namespace std;
struct edge{
    int to,cap,rev;
};
vector<edge>G[410];
int level[405],iter[405];
void addedge(int from,int to,int cap)
{
    G[from].push_back(edge{to,cap,(int)G[to].size()});
    G[to].push_back(edge{from,0,(int)G[from].size()-1});//反向容量为0!!
}
void bfs(int s)
{
    memset(level,-1,sizeof(level));
    queue<int>que;
    level[s]=0;que.push(s);
    while(!que.empty()){
        int t=que.front();que.pop();
        for(int i=0;i<G[t].size();i++){
            edge e=G[t][i];
            if(e.cap>0&&level[e.to]<0){
                level[e.to]=level[t]+1;
                que.push(e.to);
            }
        }
    }
}
int dfs(int v,int t,int f)
{
    if(v==t)return f;
    for(int&i=iter[v];i<G[v].size();i++){//注意传引用!
        edge&e=G[v][i];
        if(e.cap>0&&level[v]<level[e.to]){
            int d=dfs(e.to,t,min(f,e.cap));
            if(d>0){
                e.cap-=d;
                G[e.to][e.rev].cap+=d;
                return d;
            }
        }
    }
    return 0;//不要漏了这个,很多时候可能是无法增广的
}
int maxflow(int s,int t){
    int flow=0;
    for(;;){
        bfs(s);
        if(level[t]<0)return flow;
        memset(iter,0,sizeof(iter));
        int f;
        while(f=dfs(s,t,0x7f7f7f7f))
            flow+=f;
    }
}
int main()
{
    int n,m,i,j;int t;cin>>t;
    while(t--){
        cin>>n>>m;
        for(i=0;i<=n*2+5;i++)G[i].clear();
        for(i=1;i<=n;i++)addedge(0,i,1),addedge(i+n,n*2+1,1);
        for(i=1;i<=m;i++){
            int s,e;scanf("%d%d",&s,&e);
            addedge(s,e+n,1);
        }
        cout<<n-maxflow(0,2*n+1)<<endl;
    }

    return 0;
}

H.51Nod - 1076
双连通分量的板子题…跑完之后对于每个查询看看是不是在一个连通分量即可…
网上抄了一发，毕竟我不会双连通分量23333（强连通都基本只会抄板子，摔

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cctype>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<vector>
#include<algorithm>
using namespace std;
#define LL long long
const int maxn=25000+7;

int DFN[maxn],low[maxn],cnt=0,vis[maxn];
vector <int> edge[maxn];
stack <int> st;
void dfs(int u,int pre)
{
    vis[u]=1;
    DFN[u]=low[u]=++cnt;
    st.push(u);
    int minn=DFN[u];
    if(edge[u].size()>0)
    {
        for(int i=0;i<edge[u].size();i++)
        {
            int v=edge[u][i];
            if(v==pre) continue;
            if(!vis[v])
            {
                dfs(v,u);
            }
            minn=min(low[v],minn);
        }
    }
    low[u]=minn;
    if(low[u]==DFN[u])
    {
        while(1)
        {
            int x=st.top();
            st.pop();
            low[x]=DFN[u];
            if(x==u) break;
        }
    }
}
int main()
{
    int n,m,i,j,k,x,y;
    scanf("%d%d",&n,&m);
    for(i=1;i<=m;i++)
    {
        scanf("%d%d",&x,&y);
        edge[x].push_back(y);
        edge[y].push_back(x);
    }
    for(i=1;i<=n;i++)
    {
        if(!vis[i]) dfs(i,0);
    }
    int q;
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d%d",&x,&y);
        if(low[x]==low[y]) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

I.BZOJ 1003
SPFA+DP的问题，当然我是不会的2333
做法：
令cost[i][j]为从第i天到第j天都用同一条航线的最小花费，这个做n^2遍spfa即可（如果某个点的不可用区间跟i，j有交集，那么就标记 为不可用），得到cost数组后，设dp[i]表示前i天的最小总成本，那么考虑上一次是在第j天后变换航线（j=0,1,…,i-1，第一天选择航线也被看作是一次改变航线，算出dp[n]后再减掉多加的成本k即可），那么有以下转移方程dp[i]=min(dp[j]+cost[j+1][i]+k)，j=0,1,…,i-1，dp[n]-k即为最小总成本。注意开longlong
代码暂时有bug，待更新

#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<cstring>
using namespace std;
struct edge{
    int to,cost;
};
const int M=25;
vector<edge>G[M];
bool inque[M];
int dis[M];
int spfa(int s,int t)
{
    memset(dis,0x3f,sizeof(dis));dis[s]=0;int i,j;
    queue<int>que;que.push(s);inque[s]=true;
    while(!que.empty()){
        int t=que.front();que.pop();inque[t]=false;
        for(i=0;i<G[t].size();i++){
            edge e=G[t][i];if(inque[e.to])continue;
            if(dis[e.to]>dis[t]+e.cost){
                dis[e.to]=dis[t]+e.cost;
                if(!inque[e.to]){
                    que.push(e.to);inque[e.to]=true;
                }
            }
        }
    }
    return dis[t];
}
int main()
{
    int n,m,s,i,j,k,e,seg[25][105]={0};
    cin>>n>>m>>k>>e;
    //for(i=1;i<=n;i++)dis[i]=(1<<31)-1;
    //dis[s]=0;
    for(i=1;i<=e;i++){
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        G[a].push_back(edge{b,c});G[b].push_back(edge{a,c});
    }
    int d;cin>>d;
    while(d--){
        int p,a,b;cin>>p>>a>>b;
        for(i=a;i<=b;i++)seg[p][i]=1;
    }
    int cost[105][105]={0};
    for(i=1;i<=n;i++)
        for(j=i;j<=n;j++){
        memset(inque,0,sizeof(inque));
        for(int k=2;k<m;k++){
            for(int l=i;l<=j;l++){
                if(seg[k][l]) {
                    inque[k] = true;
                    break;
                }
            }
        }
        s=spfa(1,m);
        if(s==0x3f3f3f3f)
            cost[i][j]=0x3f3f3f3f;
        else cost[i][j]=s*(j-i+1);
    }
    int f[105];memset(f,0x3f,sizeof(f));f[0]=0;
    for(i=1;i<=n;i++){
        for(j=0;j<i;j++)
            f[i]=min(f[i],f[j]+cost[j+1][i]+k);
    }
    //for(i=1;i<=n;i++)cout<<f[i]<<endl;
    cout<<f[n]-k<<endl;

    return 0;
}

J.留个坑