さいだいりゅうさいしょうきりとり
5771 ワード
hdu3251
Being a Hero
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 867 Accepted Submission(s): 278 Special Judge
Problem Description
You are the hero who saved your country. As promised, the king will give you some cities of the country, and you can choose which ones to own!
But don't get too excited. The cities you take should NOT be reachable from the capital -- the king does not want to accidentally enter your area. In order to satisfy this condition, you have to destroy some roads. What's worse, you have to pay for that -- each road is associated with some positive cost. That is, your final income is the total value of the cities you take, minus the total cost of destroyed roads.
Note that each road is a unidirectional, i.e only one direction is available. Some cities are reserved for the king, so you cannot take any of them even if they're unreachable from the capital. The capital city is always the city number 1.
Input
The first line contains a single integer T (T <= 20), the number of test cases. Each case begins with three integers n, m, f (1 <= f < n <= 1000, 1 <= m < 100000), the number of cities, number of roads, and number of cities that you can take. Cities are numbered 1 to n. Each of the following m lines contains three integers u, v, w, denoting a road from city u to city v, with cost w. Each of the following f lines contains two integers u and w, denoting an available city u, with value w.
Output
For each test case, print the case number and the best final income in the first line. In the second line, print e, the number of roads you should destroy, followed by e integers, the IDs of the destroyed roads. Roads are numbered 1 to m in the same order they appear in the input. If there are more than one solution, any one will do.
Sample Input
Sample Output
标题:あなたにfつのオプション都市をあげて、すべての都市はすべてその価値がありますw 0、王の都市は1で、今王はあなたに会いたくありません(王はある経路を通じてあなたの選んだ都市に着きたくありません)--あなたの選んだいくつかの都市を隔離して、すべての道路の遮断はすべてw 1を費やす必要があって、今あなたに達成することができる最大の価値を聞きます あなたが切った道の番号を出力するように要求します 問題解:ネットワークフローモデル問題、すべての選択可能なポイントをスーパーポイントに接続し、エッジ権は都市の価値であり、最小割合(最大ストリームに等しい)を求め、最大値はすべての選択可能なポイントの価値と最小割合を減算する. すべての割れ目の求め方:最後にDFSは一回、源点から出発して、すべて着くことができる点はマークを行って、届かない点は自然に汇点の集合に属します
一度検索すると、異なる集合の2つの点に属するエッジがエッジを切り、この問題が入力された順序で出力されることに注意します.
プログラム:
Being a Hero
Time Limit: 20000/10000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 867 Accepted Submission(s): 278 Special Judge
Problem Description
You are the hero who saved your country. As promised, the king will give you some cities of the country, and you can choose which ones to own!
But don't get too excited. The cities you take should NOT be reachable from the capital -- the king does not want to accidentally enter your area. In order to satisfy this condition, you have to destroy some roads. What's worse, you have to pay for that -- each road is associated with some positive cost. That is, your final income is the total value of the cities you take, minus the total cost of destroyed roads.
Note that each road is a unidirectional, i.e only one direction is available. Some cities are reserved for the king, so you cannot take any of them even if they're unreachable from the capital. The capital city is always the city number 1.
Input
The first line contains a single integer T (T <= 20), the number of test cases. Each case begins with three integers n, m, f (1 <= f < n <= 1000, 1 <= m < 100000), the number of cities, number of roads, and number of cities that you can take. Cities are numbered 1 to n. Each of the following m lines contains three integers u, v, w, denoting a road from city u to city v, with cost w. Each of the following f lines contains two integers u and w, denoting an available city u, with value w.
Output
For each test case, print the case number and the best final income in the first line. In the second line, print e, the number of roads you should destroy, followed by e integers, the IDs of the destroyed roads. Roads are numbered 1 to m in the same order they appear in the input. If there are more than one solution, any one will do.
Sample Input
2
4 4 2
1 2 2
1 3 3
3 2 4
2 4 1
2 3
4 4
4 4 2
1 2 2
1 3 3
3 2 1
2 4 1
2 3
4 4
Sample Output
Case 1: 3
1 4
Case 2: 4
2 1 3
标题:あなたにfつのオプション都市をあげて、すべての都市はすべてその価値がありますw 0、王の都市は1で、今王はあなたに会いたくありません(王はある経路を通じてあなたの選んだ都市に着きたくありません)--あなたの選んだいくつかの都市を隔離して、すべての道路の遮断はすべてw 1を費やす必要があって、今あなたに達成することができる最大の価値を聞きます あなたが切った道の番号を出力するように要求します 問題解:ネットワークフローモデル問題、すべての選択可能なポイントをスーパーポイントに接続し、エッジ権は都市の価値であり、最小割合(最大ストリームに等しい)を求め、最大値はすべての選択可能なポイントの価値と最小割合を減算する. すべての割れ目の求め方:最後にDFSは一回、源点から出発して、すべて着くことができる点はマークを行って、届かない点は自然に汇点の集合に属します
一度検索すると、異なる集合の2つの点に属するエッジがエッジを切り、この問題が入力された順序で出力されることに注意します.
プログラム:
#include"stdio.h"
#include"string.h"
#include"iostream"
#define M 1009
#define inf 999999999
using namespace std;
struct st
{
int u,v,w,next;
}edge[400009];
int head[M],dis[M],q[M],work[M],cnt[M],use[M],t;
int min(int a,int b)
{
return a<b?a:b;
}
void init()
{
t=0;
memset(head,-1,sizeof(head));
}
void add(int u,int v,int w)
{
edge[t].u=u;
edge[t].v=v;
edge[t].w=w;
edge[t].next=head[u];
head[u]=t++;
edge[t].u=v;
edge[t].v=u;
edge[t].w=0;
edge[t].next=head[v];
head[v]=t++;
}
int bfs(int S,int T)
{
int rear=0;
memset(dis,-1,sizeof(dis));
dis[S]=0;
q[rear++]=S;
for(int i=0;i<rear;i++)
{
for(int j=head[q[i]];j!=-1;j=edge[j].next)
{
int v=edge[j].v;
if(edge[j].w&&dis[v]==-1)
{
dis[v]=dis[q[i]]+1;
q[rear++]=v;
if(v==T)
return 1;
}
}
}
return 0;
}
int dfs(int S,int a,int T)
{
if(S==T)
return a;
for(int &i=work[S];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(edge[i].w&&dis[v]==dis[S]+1)
{
int tt=dfs(v,min(a,edge[i].w),T);
if(tt)
{
edge[i].w-=tt;
edge[i^1].w+=tt;
return tt;
}
}
}
return 0;
}
int Dinic(int S,int T)
{
int ans=0;
while(bfs(S,T))
{
memcpy(work,head,sizeof(head));
while(int tt=dfs(S,inf,T))
ans+=tt;
}
return ans;
}
void DFS(int S)
{
use[S]=1;
for(int i=head[S];i!=-1;i=edge[i].next)
{
int v=edge[i].v;
if(!use[v]&&edge[i].w)
DFS(v);
}
}
int main()
{
int T,m,k,n,a,b,c,kk=1,i;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
init();
int sum=0;
while(m--)
{
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
while(k--)
{
scanf("%d%d",&a,&c);
add(a,n+1,c);
sum+=c;
}
printf("Case %d: ",kk++);
int ans=Dinic(1,n+1);
printf("%d
",sum-ans);
memset(use,0,sizeof(use));
DFS(1);
int r=0;
for(i=0;i<t;i+=2)
{
int u=edge[i].u;
int v=edge[i].v;
if(use[u]&&!use[v]&&v!=n+1)
cnt[r++]=i/2+1;
}
printf("%d",r);
for(i=0;i<r;i++)
printf(" %d",cnt[i]);
printf("
");
}
return 0;
}