#include<stdio.h>
#include<vector>
using namespace std;
const int N = 10100;
int tc, n, m;
int c, x, y;
vector<int> e[N+1][2];
int gr[N+1];
int fr, re, q[N+1];
int t, g[N+1], s, d;
bool dp[N+1];
int bfs(int s)
{
int i, j, k, K, p[2] = {0, 0};
fr = re = 0;
q[++re] = s, gr[s] = 0, ++p[0];
for(;fr<re;)
{
s = q[++fr];
for(k = 0; k<=1; ++k)
for(K = gr[s]^k,i = e[s][k].size()-1;i>=0;--i)
{
j = e[s][k][i];
if(gr[j] == -1)
q[++re] = j, gr[j] = k, ++p[K];
else if(gr[j] != K)
return -1;
}
}
return p[0]>p[1]?p[0]-p[1]:p[1]-p[0];
}
int main()
{
int i, j;
freopen("input.txt","r", stdin);
freopen("output.txt", "w", stdout);
for(tc = 1; tc <=5; tc++)
{
scanf("%d%d", &n, &m);
for(i = 1; i<=n;++i)
{
e[i][0].clear(),e[i][1].clear(),gr[i] = -1;
}
for(i = 0; i<m;++i)
{
scanf("%d%d%d", &c, &x, &y);
e[x][c==1].push_back(y),e[y][c==-1].push_back(x);
}
t = d = 0;
for(i = 1;i<=n;++i)
{
if(gr[i]==-1)
{
d+=g[++t]=bfs(i);
if(g[t]==-1) break;
}
}
if(i<=n) printf("-1\n");
else
{
for(i = 0; i<=n;++i) dp[i] = 0;
dp[0] = 1;
for(s = 0, i = 1; i<=t;s+=g[i++])
for(j=s;j>=0;--j)
if(dp[j]) dp[j+g[i]]=1;
for(i = d/2;!dp[i];--i);
printf("%d\n", d-2*i);
}
}
return 0;
}
이게 c++인데 c언어로좀 바꿔주실분 있나요,,, ㅠㅠ
제가 c언어밖에모르는데 c++답밖에 없어서..ㄷㄷ |
3198, 
1/160 
