被數據范圍坑死了。。。
說好的m<=10000,改成了m<=11000....
把所有最短路涉及到的邊摳出來。
然後建圖，邊的權值為邊的c。
然後對圖求一個最小割。
最小割割掉的所有的邊即為要選調的邊。
#include
#include
#include
#include
#include
using namespace std;
#define INF 99999999
const int maxn =1110;
const int maxm =25000;
const int oo = 1<<29;
struct Arclist
{
int cnt, head[maxn], dis[maxn];
int cur[maxn], pre[maxn], gap[maxn], aug[maxn];
struct node
{
int u, v, w, next;
} edge[maxm];
void init(int n)
{
cnt = 0;
std::fill_n(head, n+1, -1);
}
void add(int u, int v, int w)
{
edge[cnt].u = u;
edge[cnt].v = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
edge[cnt].u = v;
edge[cnt].v = u;
edge[cnt].w = 0;
edge[cnt].next = head[v];
head[v] = cnt++;
}
int sap(int s, int e, int n)
{
int max_flow = 0, u = s;
int mindis;
for(int i = 0; i <= n; i++)
{
cur[i] = head[i];
dis[i] = 0;
gap[i] = 0;
}
aug[s] = oo;
pre[s] = -1;
gap[0] = n;
while(dis[s]0 && dis[u]==dis[v]+1)
{
flag = true;
pre[v] = u;
cur[u] = id;
aug[v] = std::min(aug[u], edge[id].w);
u = v;
break;
}
}
if(flag==false)
{
if(--gap[dis[u]]==0) break;
mindis = n;
cur[u] = head[u];
for(int id = head[u]; id != -1; id = edge[id].next)
{
int v = edge[id].v;
if(edge[id].w>0 && dis[v]dis[i])
{
minn=dis[i];
x=i;
}
}
if(minn==INF)break;
vis[x]=1;
for(i=gs.head[x];i!=-1;i=gs.edge[i].next)
{
int v=gs.edge[i].v;
int w=gs.edge[i].w;
if(vis[v])continue;
if(dis[v]>dis[x]+w)dis[v]=dis[x]+w;
}
}
//for(i=1;i<=n;i++)cout<que;
while(!que.empty())que.pop();
que.push(ed);
memset(vis,0,sizeof(vis));
vis[ed]=1;
while(!que.empty())
{
int x=que.front();
que.pop();
if(x==st)continue;
for(i=gs.head[x];i!=-1;i=gs.edge[i].next)
{
int u=gs.edge[i].v;
int w=gs.edge[i].w;
int c=gs.edge[i].c;
if(dis[u]+w==dis[x])
{
// cout<
