No.943 Interrogation
face4
ganariyaNote
Python users are recommended to submit with PyPy.
(The code written by the writer, a Python novice, takes Python 4630ms, PyPy 240ms in the worst case)
Problem Statement
You are a veteran detective, cold-blooded and ruthless.
Having finally located the hideout of a fraud ring, you carried out a raid on the hideout and
successfully caught all $N$ members of the fraud ring.
The captured members are held one per room, in a total of $N$ interrogation rooms. Your goal is to
make all the members confess.
From the prior investigation, it is known that each member of the fraud ring relies on some number (0 or more) of other members.
When a member learns that all the members they rely on have confessed (or if they relied on no one from the beginning),
that member will lose their emotional support and confess all the wrongs they have committed.
As mentioned above, each member is placed in a separate interrogation room. In other words, whether other members have confessed
can only be learned through you. What does this mean?
You can lie to the members. Specifically, even though member $i$ has not yet confessed,
you can bluff a member $j$ other than $i$ by saying, "$i$ came clean about everything they did and got it off their chest. Why don't you do the same?"
Cold-blooded and ruthless as you are, telling the lie that $i$ has confessed makes you feel slightly
sorry toward $i$. However, habit is a frightening thing: once you have told the lie that $i$ has confessed,
you feel no sorrow at all no matter how many more times you tell the same lie (because you are cold-blooded and ruthless).
You are given the list $X$ of the members each member of the fraud ring relies on, and the sorrow $A_i$ you feel when you first tell the lie that
"member $i$ has confessed". Find the minimum possible total sorrow you must
feel in order to make all the members confess.
Note that you feel no sorrow for conveying the *fact* that a member has confessed
(see the explanation of the samples if this is unclear).
Input
$N$
$X_{11}$ $X_{12}$ $\cdots$ $X_{1N}$
$X_{21}$ $X_{22}$ $\cdots$ $X_{2N}$
$\vdots$
$X_{N1}$ $X_{N2}$ $\cdots$ $X_{NN}$
$A_1$ $A_2$ $\cdots$ $A_N$
All input values are integers.
- $1 \le N \le 18$
- $X_{ij} = 0, 1$ (1 means member $i$ relies on member $j$, 0 means they do not)
- $X_{ii} = 0$ $(1 \le i \le N)$
- $0 \le A_i \le 10^5$
Output
Output the minimum possible total sorrow you must feel in order to make all the members confess. End the output with a newline.
Sample
Sample 1
Input
3 0 1 1 1 0 0 1 0 0 5 3 3
Output
5
Let the members be $A,B,C$ in order. An example of an optimal strategy is shown below.
First, tell $B$ that $A$ has confessed. This is a lie, so you feel sorrow of 5. $B$ confesses.
Next, tell $C$ that $A$ has confessed. This is a lie, but you have already told this lie once, so
you feel no sorrow here. $C$ confesses.
Finally, tell $A$ that $B$ and $C$ have confessed. This is true, so you feel no sorrow. $A$ confesses.
You made all the members confess with sorrow 5. It is impossible to make all the members confess
with sorrow less than 5, so output 5.
Sample 2
Input
3 0 1 1 1 0 0 1 0 0 10 1 1
Output
2
Let the members be $A,B,C$ in order. An example of an optimal strategy is shown below.
First, tell $A$ that $B,C$ have confessed. Both of these are lies, so you feel sorrow of $1+1=2$. $A$ confesses.
Next, tell $B$ and $C$ that $A$ has confessed. This is true, so you feel no sorrow. $B$ and $C$ confess.
You made all the members confess with sorrow 2. It is impossible to make all the members confess
with sorrow less than 2, so output 2.
Sample 3
Input
3 0 1 1 1 0 1 1 1 0 1 2 4
Output
3
Let the members be $A,B,C$ in order. An example of an optimal strategy is shown below.
First, tell $C$ that $A,B$ have confessed. Both of these are lies, so you feel sorrow of $1+2=3$. $C$ confesses.
Next, tell $B$ that $A,C$ have confessed. That $C$ has confessed is true, so you feel no sorrow for it.
That $A$ has confessed is a lie, but you have already told this lie once, so again you feel no sorrow.
$B$ confesses.
Tell $A$ that $B,C$ have confessed. Both of these are true, so you feel no sorrow. $A$ confesses.
You made all the members confess with sorrow 3. It is impossible to make all the members confess
with sorrow less than 3, so output 3.
Sample 4
Input
4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 10 10 10
Output
0
No one relies on anyone, so everyone confesses from the beginning. The sorrow is just 0.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。