链接
题面
题解
状压dp
这个方法官方题解里面写得还挺好的。
我就不写全了。仅仅简单地记录一下而已。
- 我们考虑最终这幅图相当于说你给他分个层，使得每条边都从深度浅的连向深度深的。
- 首先我们能用一些方法把边权变成点权。这样事情就由深度差乘边权变成了深度乘点权。好处理多了。
- 分层了之后，自然就有一个结论：层数不超过点数。
- 分层了，那我们就用状压dp，记(dp_{i,j})表示当前分完了第i层，已经分好了的集合为j。
- 现在我们可以枚举子集转移了，复杂度(O(n3^n))。
- 我们希望能枚举点转移。但是硬转移肯定是不行的，因为我们有可能连出在同一层的边。那我们同一层的点拓扑排序完了之后倒叙添加就不会有这种事情了。
最小割
- 我们同样边权变点权。记点权为(a_i)
- 我们对于每个点分出一组n个点，编号从1到n，分别表示这个点选择这个深度，并由第i组点的第j个点向该组第j+1个点连一条((j+1)a_i)的边。这样我们就可以计算出代价了，接下来我们要加限制。
- 限制，如果有一条边(x,y)，那么对于每个深度的x的点向最浅的一直到下个深度的y的点连一条INF边。
- 注意到可能会有负权边。考虑到每一组的计算代价的边会且只会割一条。那我们给这些边统一加一个超级大数就行了。具体来说，这个超级大数可以参考最小的负权边来定。
- 最后最小割，用一个bfs走还能走的边给点染色。然后看看那些从被染色的点到没被染色的点的边就是被割掉边。
代码
状压dp
#include<bits/stdc++.h>
#define LL long long
#define MAXN 18
#define INF 1000000000000
using namespace std;
template<typename T> void Read(T &cn)
{
char c; int sig = 1;
while(!isdigit(c = getchar())) if(c == '-') sig = 0;
if(sig) {cn = c-48; while(isdigit(c = getchar())) cn = cn*10+c-48; }
else {cn = 48-c; while(isdigit(c = getchar())) cn = cn*10+48-c; }
}
template<typename T> void Write(T cn)
{
int wei = 0; T cm = 0; int cx = cn%10; cn/=10;
if(cn < 0 || cx < 0) {putchar('-'); cn = 0-cn; cx = 0-cx; }
while(cn)cm = cm*10+cn%10,cn/=10,wei++;
while(wei--)putchar(cm%10+48),cm/=10;
putchar(cx+48);
}
template<typename T> void WriteL(T cn) {Write(cn); puts(""); }
template<typename T> void WriteS(T cn) {Write(cn); putchar(' '); }
template<typename T> void Max(T &cn, T cm) {cn = cn < cm ? cm : cn; }
template<typename T> void Min(T &cn, T cm) {cn = cn < cm ? cn : cm; }
int n,m;
struct Dp_lai{
int a[MAXN+1];
LL ans;
void qing() {ans = INF; memset(a,0,sizeof(a)); }
void outit() {for(int i = 1;i<=n;i++) WriteS(a[i]); puts(""); }
};
int e[MAXN+1][MAXN+1], g[MAXN+1];
LL de[MAXN+1];
Dp_lai f[1<<MAXN];
int du[MAXN+1], dui[MAXN+1];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
Read(n); Read(m);
for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) e[i][j] = 0;
memset(du,0,sizeof(du)); memset(de,0,sizeof(de));
for(int i = 1;i<=m;i++) {int bx,by; LL bz; Read(bx); Read(by); Read(bz); e[by][bx] = 1; de[bx] += bz; de[by] -= bz; du[bx]++; }
for(int i = 1;i<=n;i++)
{
g[i] = 0;
for(int j = 1;j<=n;j++) if(e[j][i]) g[i] |= 1<<(j-1);
}
int l = 0, r = 0;
for(int i = 1;i<=n;i++) if(!du[i]) dui[++r] = i;
while(l < r)
{
int dang = dui[++l];
for(int i = 1;i<=n;i++) if(e[dang][i])
{
du[i]--;
if(!du[i]) dui[++r] = i;
}
}
for(int i = 0;i<(1<<n);i++) f[i].qing();
f[0].ans = 0;
for(int i = 1;i<=n;i++) for(int j = n;j>=1;j--) for(int k = 0;k<(1<<n);k++)
{
int bx = dui[j];
if(((k&(1<<(bx-1)))!=0) || ((k&g[bx])!=g[bx]) || (f[k].ans+i*de[bx] >= f[k|(1<<(bx-1))].ans)) continue;
f[k|(1<<(bx-1))] = f[k]; f[k|(1<<(bx-1))].ans += i*de[bx]; f[k|(1<<(bx-1))].a[bx] = i;
}
f[(1<<n)-1].outit();
return 0;
}
最小割
#include<bits/stdc++.h>
#define LL long long
#define MAXN 20
#define INF 1000000000
using namespace std;
template<typename T> void Read(T &cn)
{
char c; int sig = 1;
while(!isdigit(c = getchar())) if(c == '-') sig = 0;
if(sig) {cn = c-48; while(isdigit(c = getchar())) cn = cn*10+c-48; }
else {cn = 48-c; while(isdigit(c = getchar())) cn = cn*10+48-c; }
}
template<typename T> void Write(T cn)
{
int wei = 0; T cm = 0; int cx = cn%10; cn/=10;
if(cn < 0 || cx < 0) {putchar('-'); cn = 0-cn; cx = 0-cx; }
while(cn)cm = cm*10+cn%10,cn/=10,wei++;
while(wei--)putchar(cm%10+48),cm/=10;
putchar(cx+48);
}
template<typename T> void WriteL(T cn) {Write(cn); puts(""); }
template<typename T> void WriteS(T cn) {Write(cn); putchar(' '); }
template<typename T> void Max(T &cn, T cm) {cn = cn < cm ? cm : cn; }
template<typename T> void Min(T &cn, T cm) {cn = cn < cm ? cn : cm; }
namespace Flow{
const int MAXB = MAXN*MAXN*MAXN*MAXN;
const int MAXD = MAXN*MAXN+2;
struct qwe{
int a,b,ne,f;
void mk(int ca, int cb, int cn, int cf) {a = ca; b = cb; ne = cn; f = cf; }
};
qwe a[MAXB*2+1];
int alen;
int head[MAXD+1], lst[MAXD+1];
int shen[MAXD+1], dui[MAXD+1];
int typ[MAXD+1];
int bfs(int cn, int cm, int ctot)
{
for(int i = 1;i<=ctot;i++) shen[i] = ctot+2, lst[i] = head[i];
int l = 0, r = 0; dui[++r] = cn; shen[cn] = 0;
while(l < r)
{
int dang = dui[++l];
for(int i = head[dang];i;i = a[i].ne)
{
int y = a[i].b;
int lin = shen[dang]+1;
if(!a[i].f || shen[y] <= lin) continue;
shen[y] = lin; dui[++r] = y;
}
}
return shen[cm] != ctot+2;
}
LL ansl;
int dfs(int cn, int cm, int liu)
{
if(cn == cm) {ansl = ansl + liu; return liu; }
for(int &i = lst[cn];i;i = a[i].ne)
{
int y = a[i].b;
if(!a[i].f || shen[y] != shen[cn]+1) continue;
int lin = dfs(y, cm, min(liu, a[i].f));
if(lin) {
a[i].f -= lin;
a[((i+1)^1)-1].f += lin;
return lin;
}
}
return 0;
}
void get_typ(int cn, int ctot)
{
for(int i = 1;i<=ctot;i++) shen[i] = 0, typ[i] = 0;
int l = 0, r = 0; shen[cn] = 1; typ[cn] = 1; dui[++r] = cn;
while(l < r)
{
int dang = dui[++l];
for(int i = head[dang];i;i = a[i].ne)
{
int y = a[i].b;
if(!a[i].f) continue;
typ[y] = 1; if(!shen[y]) shen[y] = 1, dui[++r] = y;
}
}
}
void flow(int cn, int cm, int ctot)
{
while(bfs(cn,cm,ctot)) while(dfs(cn,cm,INF));
get_typ(cn, ctot);
}
void build() {alen = 0; memset(head,0,sizeof(head)); }
void lian(int cn, int cm, int cf) {a[++alen].mk(cn,cm,head[cn],cf); head[cn] = alen; }
void lian_d(int cn, int cm, int cf) {lian(cn,cm,cf), lian(cm,cn,0); }
};
using Flow::build;
using Flow::lian_d;
using Flow::flow;
int n, m;
int e[MAXN+1][MAXN+1];
int de[MAXN+1];
int ans[MAXN+1];
int pos[MAXN+1][MAXN+1];
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
Read(n); Read(m);
for(int i = 1;i<=n;i++) for(int j = 1;j<=n;j++) e[i][j] = 0;
memset(de,0,sizeof(de));
for(int i = 1;i<=m;i++) {int bx,by; LL bz; Read(bx); Read(by); Read(bz); e[by][bx] = 1; de[bx]+=bz; de[by]-=bz; }
LL xiao = 0;
for(int i = 1;i<=n;i++) Min(xiao, (LL)de[i]); xiao = xiao*n-1;
// printf("xiao = %lld
",xiao);
build();
for(int i = 1;i<=n;i++)
{
int lst = 1;
for(int j = 1;j<=n;j++)
{
int xian = 1+n*(i-1)+j;
lian_d(lst, xian, de[i]*j-xiao);
pos[i][j] = Flow::alen;
// printf(" %d
",Flow::a[pos[i][j]].f);
for(int k = 1;k<=n;k++) if(e[i][k]) lian_d(lst, 1+n*(k-1)+j, INF);
lst = xian;
}
lian_d(lst, 1+n*n+1, INF);
}
// printf("pred
");
flow(1, 1+n*n+1, 1+n*n+1);
// printf("flow over
");
for(int i = 1;i<=n;i++)
{
int lst = 1;
for(int j = 1;j<=n;j++)
{
int xian = 1+n*(i-1)+j;
if(Flow::typ[lst] == 1 && Flow::typ[xian] == 0) ans[i] = j;
lst = xian;
}
}
for(int i = 1;i<=n;i++) WriteS(ans[i]); puts("");
return 0;
}