最後答案輸出兩行：第一行輸出最多能 修復多少個城市。 第二行輸出1操作對應的每年修復的城市個數（輸出的序列字典序最小）。
解題：最小費用最大流。首先用二維數組記錄路的連接狀況。建圖：把年數也看作一個點year+n 並與超極源點vs建邊，邊容為k，費用為m（m為遞減的,這樣加一個費用是為了找出字典序最小的解（先流向年限最大的））則該邊為< vs , year+n , k , m> 。如果遇到操作1 ，那麼就用bfs或dfs找出與x相連的點Y，再新增一些邊< year+n , Y , 1 , 0 > ，最後再連接每個 i 城市與超極匯點 vt 的邊 < i , vt , 1 , 0 > ，邊容為1是因為每個城市只能修復 1 次。最後跑一次最小費用最大流 ，最大流就是最多能修復的城市，源點流向每一年的流最就是每年可修復的城市數量。
#include
#include
#include
using namespace std;
const int MAXN = 1010;
const int MAXM = 100100;
const int INF = 1<<30;
struct EDG{
int to,next,cap,flow;
int cost; //單價
}edg[MAXM];
int head[MAXN],eid;
int pre[MAXN], cost[MAXN] ; //點0~(n-1)
void init(){
eid=0;
memset(head,-1,sizeof(head));
}
void addEdg(int u,int v,int cap,int cst){
edg[eid].to=v; edg[eid].next=head[u]; edg[eid].cost = cst;
edg[eid].cap=cap; edg[eid].flow=0; head[u]=eid++;
edg[eid].to=u; edg[eid].next=head[v]; edg[eid].cost = -cst;
edg[eid].cap=0; edg[eid].flow=0; head[v]=eid++;
}
bool inq[MAXN];
int q[MAXN];
bool spfa(int sNode,int eNode,int n){
int l=0 , r=0;
for(int i=0; i0 && cost[v]>cost[u]+edg[i].cost){ //在滿足可增流的情況下，最小花費
cost[v] = cost[u]+edg[i].cost;
pre[v]=i; //記錄路徑上的邊
if(!inq[v]){
if(r==MAXN)r=0;
q[r++]=v;
inq[v]=1;
}
}
}
}
return cost[eNode]!=INF; //判斷有沒有增廣路
}
//反回的是最大流，最小花費為minCost
int minCost_maxFlow(int sNode,int eNode ,int& minCost,int n){
int ans=0;
while(spfa(sNode,eNode,n)){
int mint=INF;
for(int i=pre[eNode]; i!=-1; i=pre[edg[i^1].to]){
if(mint>edg[i].cap-edg[i].flow)
mint=edg[i].cap-edg[i].flow;
}
ans+=mint;
for(int i=pre[eNode]; i!=-1; i=pre[edg[i^1].to]){
edg[i].flow+=mint; edg[i^1].flow-=mint;
minCost+=mint*edg[i].cost;
}
}
return ans;
}
int vist[MAXN],mapt[MAXN][MAXN],year;
void bfs(int u , int n)//找出與u相連的點
{
queueq;
memset(vist,0,sizeof(vist));
vist[u]=1;
q.push(u);
while(!q.empty())
{
u=q.front(); q.pop();
for(int i=1; i<=n; i++)
if(!vist[i]&&mapt[u][i])
vist[i]=1,q.push(i);
}
for(int i=1; i<=n; i++)
if(vist[i])
addEdg(year+n , i , 1 , 0);
}
int main()
{
int n,m,k ,op , u ,v;
int T;
scanf(%d,&T);
while(T--)
{
scanf(%d%d%d,&n,&m,&k);
memset(mapt,0,sizeof(mapt));
init();
year=0;
int vs=0 ,vt = n+m+1;
for(int i=1; i<=n; i++)
addEdg(i , vt , 1 , 0);
while(m--){
scanf(%d%d,&op,&u);
if(op==3) {
int p=u ;
while(p--){
scanf(%d%d,&u,&v);
mapt[u][v]=mapt[v][u]=0;
}
}
else{
if(op==2){
scanf(%d,&v);
mapt[u][v]= mapt[v][u]=1;
}
else{
year++;
addEdg(vs , year+n , k , m);
bfs(u , n);
}
}
}
int ans,tans[505] ;
ans=minCost_maxFlow(vs , vt , m , vt+1);
for(int i=head[vs]; i!=-1; i=edg[i].next )
tans[edg[i].to-n]=edg[i].flow;
printf(%d
,ans);
for(int i=1; i<=year; i++)
if(i
