一个国家由n个城市组成，任意两个城市间都有一条双向的道路。如今，恐怖分子想要炸掉其中的一些道路，使得这n个城市变得不再连通，也就是说，存在至少两个城市，它们之间不可通过道路互相到达。要炸毁一条道路需要一定的代价。请你计算一下要使恐怖分子达到它们的目的，所需要的最小总代价是多少。结果说明：破坏道路(1,3),(1,4),(2,3),(2,4)可以使城市1，2与城市3，4之间无法到达，所需的最小总代价为4
input：
第一行为正整数n (n ≤ 50)，表示城市的个数，接下来的n行每行由n个0~9之间的数字组成，数字之间没有空格或任何其他字符间隔，第i行的第j个数字表示要破坏城市i与城市j之间的道路所需要的代价。输入数据保证对于任意i, j。第i行的第j个数字与第j行的第i个数相等，且对于所有的i，第i行的第i个数字都等于0
output：
输出仅有一个整数，即要破坏这n个城市的连通性，所需要的最小总代价
input：
4
0911
9011
1109
1190
output：
4
思路：
一看此题便知道是最小割问题，对于最小割问题可以等价于最大流来求解，本人正是运用了最大流来求解的。刚开始做的时后看着哪个 <邻接矩阵>就知道了是无向图，但是网络流是对于有向图而言，但是无向的就把我个搞的有点糊里糊涂，而且再“后悔”哪个步骤那里（c[pre[i]][i]+=minflow;c[i][pre[i]]-=minflow）那里我加了c[i][pre[i]]-=minflow此句话也AC，不加也AC，于是我就反糊涂了，对于有向图而言“后悔”是必定要的，但是无向图是否也有必要了，这个问题打扰了我好久。
请前来浏览者，如果知道无向图是否需要“反悔”这个道理，请告诉我，我什么的谢谢。
【参考程序】：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
long c[51][51],flow[51][51],queue[51],pre[51],n,ans,sumflow;
bool visit[51];
long find_minflow(long x,long y)
{
if (x>y) return y;
else return x;
}
void change_flow(long sink)
{
long minflow,i;
minflow=0xfffffff;
i=sink;
while (i!=1)
{
minflow=find_minflow(minflow,flow[pre[i]][i]);
i=pre[i];
}
sumflow+=minflow;
i=sink;
while (i!=1)
{
flow[pre[i]][i]-=minflow;
// flow[i][pre[i]]+=minflow;
i=pre[i];
}
}
void find_flow(long sink)
{
long head,tail,start,i;
for (i=1;i<=n;i++)
{
pre[i]=0;
visit[i]=false;
}
head=tail=1;visit[1]=true;
queue[head]=1;
while (head<=tail)
{
start=queue[head];
for (i=1;i<=n;i++)
if (!visit[i] && flow[start][i]>0)
{
visit[i]=true;
tail++;
queue[tail]=i;
pre[i]=start;
}
head++;
}
}
int main()
{
scanf("%d\n",&n);
char cc;
for (int i=1;i<=n;i++)
{
for (int j=1;j<=n;j++)
{
scanf("%c",&cc);
c[i][j]=cc-'0';
}
getchar();
}
ans=0x7fffffff;
long k,i;
for (i=2;i<=n;i++)
{
k=i;sumflow=0;
memcpy(flow,c,sizeof(long)*(51*51));
for (;;)
{
find_flow(k);
if (!visit[k]) break;
change_flow(k);
}
if (sumflow<ans) ans=sumflow;
}
printf("%d\n",ans);
return 0;
}