[Acwing] 1013. 机器分配 分组背包+路径输出

前言

对我来说感觉不应是绿色啊。。

传送门 :

思路

选 j j j台的机器抽象成体积,然后直接跑一遍分组背包

但是这个路径输出怎么办呢

。。拓扑的直接dfs

我们可以从后往前dfs求出终点状态是从哪一个状态转移过来的

然后我们在网上继续dfs

CODE

// Problem: 混合背包问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/7/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// Problem: P2738 [USACO4.1]���ʻ�·Fence Loops
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2738
// Memory Limit: 125 MB
// Time Limit: 1000 ms
//
// Powered by CP Editor (https://cpeditor.org)

#include 
using namespace std;
#define ll long long
#define endl '\n'
#define px first
#define py second
#define pb push_back
typedef pair pii;
int dxy[4][2] = {{-1,0},{0,1},{1,0},{0,-1}};
const int N  = 30;



struct union_find_set{
    int n,p[N];

    void init(int N)
    {
        n = N;
        for(int i=1;in>>m;
	for(int i=1;iw[i][j];
	
	
	for(int i=1;i