洛谷6

https://www.luogu.com.cn/problem/P1111

求最小生成树干什么啊难道不是个并查集板子

我本来是想要最小生成树的。。。。

https://www.luogu.com.cn/problem/P1113

有点拓扑排序的感觉，但因为可以同时执行多个任务，因此更简单了,大佬的dp解法：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,l,t,ans[10005],maxans;
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%d",&i);
        scanf("%d",&l);
        int tmp=0;
        while(scanf("%d",&t)&&t)
            tmp=max(ans[t],tmp);
        ans[i]=tmp+l;
        maxans=max(ans[i],maxans);
    } 
    printf("%d\n",maxans);
    return 0;
 }

https://vjudge.net/problem/POJ-3279

#include <cstdio>
#include <queue>
#include <string.h>
#include <iostream>
using namespace std;
int N, M;
int tile[20][20];
int turn[20][20];
int ans[20][20];
int direct[4][2] = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
int opposite(int x){
    if(x==0)
        return 1;
    return 0;
}
int solve(){
    int flag = 0;
    int New[20][20];
    for (int i = 1;i<=N;i++)
    {
        for (int j = 1;j<=M;j++){
            New[i][j] = tile[i][j];
        }
    }
    for (int i = 1; i <= N;i++){
        for (int j = 1;j<=M;j++){
            if(i!=1&&New[i-1][j]==1)
                turn[i][j] = 1;
            if(turn[i][j]==1){
                New[i][j] = opposite(New[i][j]);
                for (int k = 0; k < 4;k++){
                    int tempx = i + direct[k][0];
                    int tempy = j + direct[k][1];
                    New[tempx][tempy] = opposite(New[tempx][tempy]);
                }
            }
        }
    }
    int ret = 0;
    for (int i = 1;i<=N;i++){
        for (int j = 1; j <= M;j++){
            ret += turn[i][j];
        }
    }
    for (int i = 1;i<=M;i++){
        if(New[N][i]!=0){
            flag = 1;
            break;
        }
    }
    if(!flag)
        return ret;
    return -1;
}
void copy_toans(){
  for(int i=1;i<=N;i++)
    for(int j=1;j<=M;j++)
        ans[i][j]=turn[i][j];
}
int main(){
    cin>>N>>M;
    for (int i = 1;i<=N;i++){
        for (int j = 1; j <= M;j++){
            scanf("%d", &tile[i][j]);
        }
    }
    int t = 0;
    int ans_min = 0xfffffff;
    for (int i = 0; i < (1 << M);i++){
        memset(turn, 0, sizeof(turn));
        for (int j = 0; j < M;j++){
            if(i&(1<<j))
                turn[1][j + 1] = 1;
            
        }
        int temp = solve();
        if(temp!=-1){
            t=1;
            if(temp<ans_min){
                copy_toans();
                ans_min = temp;
            }
        }
    }
    if(t){
        for (int i = 1;i<=N;i++){
            for (int j = 1;j<=M;j++)
                printf("%d ", ans[i][j]);
            cout << endl;
        }
    }
    else
        cout << "IMPOSSIBLE" << endl;
    return 0;
}