題目描述

傳送門

題解

首先考慮如何求出第一問 要求邊權和最小 按位分開考慮，實際上就是讓這一位上的1盡量少 對于每一個點i，如果這一位已經確定，那么0:s->i,inf，1:i->t,inf 對于每一條邊，將兩個端點x,y，x->y,1；y->x,1 這樣跑最小割

據說這樣跑完最小割了之后加一個限流然后跑費用流是可以的 不過有一個非常巧妙的方法能將這兩問的答案一起求出來 同樣按位分開考慮，同樣是想要1盡量少 對于每一個點i，如果這一位已經確定，那么0:s->t,inf，1:i->t,inf；如果這一位沒有確定，那么s->i,1 對于每一條邊，將兩個端點x,y，x->y,n+1；y->x,n+1 這樣跑出來最小割，令x=ans/(n+1)，y=ans%(n+1) 可以發(fā)現x即為第一位的答案，也就是邊權和最少個數的1 y的含義即為點權和最少個數的1

代碼