2014
03-13

# Being a Hero

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.

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.

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.

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

Case 1: 3
1 4
Case 2: 4
2 1 3

/*

*/
#include <stdio.h>
#include <time.h>
#include <algorithm>
#include <map>
#include <string.h>
#include<queue>
#include<iostream>
#define N 60010
using namespace std;
const int maxn=1009;
const int inf=1<<30;
int n,m,f;
//**************************************************
//为dinic求最大流模版
struct edge
{
int v, next;
int val;
} net[ 200010 ];
int Qnum;  //记录左侧点的数量
int level[maxn], Qu[maxn], out[maxn],next[maxn],ins[maxn],first[maxn];
class Dinic {
public:
int end;
int now;
int low,high;
Dinic() {
end = 0;
memset( next, -1, sizeof(next) );
}
inline void insert( int x, int y, int c) {
net[end].v = y, net[end].val = c,
net[end].next = next[x],
next[x] = end ++;
net[end].v = x, net[end].val = 0,
net[end].next = next[y],
next[y] = end ++;
}
bool BFS( int S, int E ) {
memset( level, -1, sizeof(level) );
low = 0, high = 1;
Qu[0] = S, level[S] = 0;
for( ; low < high; ) {
int x = Qu[low];
for( int i = next[x]; i != -1; i = net[i].next ) {
if( net[i].val == 0 ) continue;
int y = net[i].v;
if( level[y] == -1 ) {
level[y] = level[x] + 1;
Qu[ high ++] = y;
}
}
low ++;
}
return level[E] != -1;
}

int MaxFlow( int S, int E ){
int maxflow = 0;
for( ; BFS(S, E) ; ) {
memcpy( out, next, sizeof(out) );
now = -1;
for( ;; ) {
if( now < 0 ) {
int cur = out[S];
for(; cur != -1 ; cur = net[cur].next )
if( net[cur].val && out[net[cur].v] != -1 && level[net[cur].v] == 1 )
break;
if( cur >= 0 ) Qu[ ++now ] = cur, out[S] = net[cur].next;
else break;
}
int u = net[ Qu[now] ].v;
if( u == E ) {
int flow = inf;
int index = -1;
for( int i = 0; i <= now; i ++ ) {
if( flow > net[ Qu[i] ].val )
flow = net[ Qu[i] ].val, index = i;
}
maxflow += flow;
for( int i = 0; i <= now; i ++ )
net[Qu[i]].val -= flow, net[Qu[i]^1].val += flow;
for( int i = 0; i <= now; i ++ ) {
if( net[ Qu[i] ].val == 0 ) {
now = index - 1;
break;
}
}
}
else{
int cur = out[u];
for(; cur != -1; cur = net[cur].next )
if (net[cur].val && out[net[cur].v] != -1 && level[u] + 1 == level[net[cur].v])
break;
if( cur != -1 )
Qu[++ now] = cur, out[u] = net[cur].next;
else out[u] = -1, now --;
}
}
}
Qnum=high;//一定要记录此时在Qu数组里点的个数，方便后面枚举
return maxflow;
}
};

struct E
{
int v,next;
}edg[200011];
int ans;
void init(int k)
{
int u,v,w;
scanf("%d%d%d",&n,&m,&f);
memset(ins,0,sizeof(ins));
memset(first,-1,sizeof(first));
Dinic my;
int edg_num=1;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
edg[i].v=v;
edg[i].next=first[u];
first[u]=i;
my.insert(u,v,w);
}
int sum=0;
for(int i=0;i<f;i++)
{
scanf("%d%d",&u,&w);
my.insert(u,n+1,w);
sum+=w;
}
printf("Case %d: %d\n",k,sum-my.MaxFlow(1,n+1));
sum=0;
for(int i=0;i<Qnum;i++)
ins[Qu[i]]=1;//标记所有左侧的点
ans=0;
//dfs(1);
for(int i=0;i<Qnum;i++)
{
int x=Qu[i];
for(int j=first[x];j!=-1;j=edg[j].next)
{
if(!ins[edg[j].v])
out[ans++]=j;
}
}
printf("%d",ans);
for(int i=0;i<ans;i++)
{
printf(" %d",out[i]);
}
printf("\n");
}
int main()
{
int Case;
scanf("%d",&Case);
for(int i=1;i<=Case;i++)
{
init(i);
//solve();
}
return 0;
}

1. 问题3是不是应该为1/4 .因为截取的三段，无论是否能组成三角形， x， y-x ，1-y,都应大于0，所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

2. [email protected]