头像

奥利你个奥




离线:2小时前


最近来访(3)
用户头像
小小_88
用户头像
1eave
用户头像
R-O-Y

活动打卡代码 AcWing 4. 多重背包问题

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, m;
int v[N], w[N], s[N];
int f[N][N];

int main()
{
    cin >> n >> m;

    for (int i = 1; i <= n; i++) cin >> v[i] >> w[i] >> s[i];

    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= m; j++)
            for (int k = 0; k * v[i] <= j && k <= s[i]; k++)
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + w[i] * k);

    cout << f[n][m] << endl;

    return 0;
}


活动打卡代码 AcWing 282. 石子合并

#include <iostream>

using namespace std;

const int N = 310;

int n;
int s[N];//前缀和
int f[N][N];

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> s[i], s[i] += s[i - 1];

    for(int len=2;len<=n;len++)
        for (int i = 1; i + len - 1 <= n; i++)
        {
            int j = len - 1 + i;
            f[i][j] = 1e8;
            for (int k = i; k < j; k++)
                f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j] + s[j] - s[i - 1]);
        }

    cout << f[1][n] << endl;

    return 0;
}


活动打卡代码 AcWing 3. 完全背包问题

朴素写法

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int w[N], v[N];
int f[N][N];

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

    for(int i=1;i<=n;i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i])
                f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;
    return 0;
}

优化

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int w[N], v[N];
int f[N];

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

    for(int i=1;i<=n;i++)
        for (int j = v[i]; j <= m; j++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

    cout << f[m] << endl;
    return 0;
}


活动打卡代码 AcWing 2. 01背包问题

朴素写法

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 1010;

int n, m;
int w[N], v[N];
int f[N][N];

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

    for(int i=1;i<=n;i++)
        for (int j = 0; j <= m; j++)
        {
            f[i][j] = f[i - 1][j];
            if (j >= v[i]) f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i]);
        }

    cout << f[n][m] << endl;

    return 0;
}


活动打卡代码 AcWing 854. Floyd求最短路

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

using namespace std;

const int N=210,INF=1e9;

int n,m,Q;
int d[N][N];

void floyd()
{
    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]);
}

int main()
{
    cin>>n>>m>>Q;

    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            if(i==j) d[i][j]=0;
            else d[i][j]=INF;

    while(m--)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);

        d[a][b]=min(d[a][b],w);
    }

    floyd();

    while(Q--)
    {
        int a,b;
        scanf("%d%d",&a,&b);

        if(d[a][b]>INF/2) cout<<"impossible"<<endl;
        else cout<<d[a][b]<<endl;
    }

    return 0;
}


活动打卡代码 AcWing 852. spfa判断负环

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

using namespace std;

const int N=100010;

int n,m;
int h[N],e[N],ne[N],w[N],idx;
bool st[N];
int dist[N];
int cnt[N];

void add(int x,int y,int c)
{
    w[idx]=c;
    e[idx]=y;
    ne[idx]=h[x];
    h[x]=idx++;
}

bool spfa()
{

    queue<int>q;

    for(int i=1;i<=n;i++)
    {
        st[i]=true;
        q.push({i});
    }

    while(q.size())
    {
        int t=q.front();
        q.pop();

        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                cnt[j]=cnt[t]+1;
                if(cnt[j]>=n) return true;
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}

int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof h);

    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    if(spfa()) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}


活动打卡代码 AcWing 851. spfa求最短路

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

using namespace std;

const int N=100010;

int n,m;
int h[N],e[N],ne[N],w[N],idx;
bool st[N];
int dist[N];

void add(int x,int y,int c)
{
    w[idx]=c;
    e[idx]=y;
    ne[idx]=h[x];
    h[x]=idx++;
}

int spfa()
{
    memset(dist,0x3f,sizeof dist);
    dist[1]=0;

    queue<int>q;
    q.push(1);

    st[1]=true;

    while(q.size())
    {
        int t=q.front();
        q.pop();

        st[t]=false;
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(dist[j]>dist[t]+w[i])
            {
                dist[j]=dist[t]+w[i];
                if(!st[j])
                {
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return dist[n];
}

int main()
{
    cin>>n>>m;

    memset(h,-1,sizeof h);

    for(int i=0;i<m;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }

    int t=spfa();

    if(t==0x3f3f3f3f) cout<<"impossible"<<endl;
    else cout<<t<<endl;

    return 0;
}



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

using namespace std;

const int N=510,M=10010;

int n,m,k;
int d[N],backup[N];

struct Edge
{
    int a,b,w;  
}edges[M];

int bellman_ford()
{
    memset(d,0x3f,sizeof d);
    d[1]=0;

    for(int i=0;i<k;i++)
    {
        memcpy(backup,d,sizeof d);
        for(int j=0;j<m;j++)
        {
            int a=edges[j].a,b=edges[j].b,w=edges[j].w;
            d[b]=min(d[b],backup[a]+w);
        }
    }
    return d[n];
}

int main()
{
    cin>>n>>m>>k;

    for(int i=0;i<m;i++)
    {
        int a,b,w;
        scanf("%d%d%d",&a,&b,&w);
        edges[i]={a,b,w};
    }

    bellman_ford();

    if(d[n] > 0x3f3f3f3f / 2) cout<<"impossible"<<endl;
    else cout<<d[n]<<endl;

    return 0;
}



//堆优化版的Dijkstra算法   针对针对单源最短路中边权都为正的稀疏图
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
const int N = 150010;

int h[N], e[N], ne[N], w[N], idx;
int d[N];
bool st[N];

int n, m;

void add(int x, int y, int c)
{
    w[idx] = c;
    e[idx] = y;
    ne[idx] = h[x];
    h[x]=idx++;
}

int dijkstra()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;    //小根堆

    heap.push({ 0,1 }); //first必须为距离
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] > distance + w[i])
            {
                d[j] = distance + w[i];
                heap.push({ d[j],j });
            }
        }
    }

    if (d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d%d", &n, &m);

    while (m--)
    {
        int x, y, c;
        scanf("%d%d%d", &x, &y, &c);
        add(x, y, c);
    }

    cout << dijkstra() << endl;

    return 0;
}



//堆优化版的Dijkstra算法   针对针对单源最短路中边权都为正的稀疏图
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
const int N = 150010;

int h[N], e[N], ne[N], w[N], idx;
int d[N];
bool st[N];

int n, m;

void add(int x, int y, int c)
{
    w[idx] = c;
    e[idx] = y;
    ne[idx] = h[x];
    h[x]=idx++;
}

int dijkstra()
{
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;    //小根堆

    heap.push({ 0,1 }); //first必须为距离
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();

        int ver = t.second, distance = t.first;

        if (st[ver]) continue;
        st[ver] = true;

        for (int i = h[ver]; i != -1; i = ne[i])
        {
            int j = e[i];
            if (d[j] > distance + w[i])
            {
                d[j] = distance + w[i];
                heap.push({ d[j],j });
            }
        }
    }

    if (d[n] == 0x3f3f3f3f) return -1;
    return d[n];
}

int main()
{
    memset(h, -1, sizeof h);
    scanf_s("%d%d", &n, &m);

    while (m--)
    {
        int x, y, c;
        scanf_s("%d%d%d", &x, &y, &c);
        add(x, y, c);
    }

    cout << dijkstra() << endl;

    return 0;
}